Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider all connected simple graphs with diameter $d = 2$ and maximal vertex degree $\Delta$. In my particular practical case $\Delta = 4$, but general problem is much more interesting — probably there exists a research on general case.

I know that, given $d = 2$ and $\Delta = 4$, the maximal number of vertices in the proper graph is $V = 15$ (the corresponding graph is K3 * C5). The question is: given $V$, how can one find the proper $V$-vertex graph with minimal number of edges?

I wrote the simple brute-force program and found the answer for all $V \le 8$. But calculating it further using this approach is going to take a tremendous amount of time, so I decided to ask the community for any advices or links to researches. Thank you for any assistance.

P.S. Sorry, if my English wasn't understandable enough.

P.P.S. Firstly I asked this question at MathOverflow, but later I realized that it would be more appropriate here. Sorry for redundancy.

share|cite|improve this question
So if I read correctly, your problem is the following: Given Delta, d, n, find the graph with diameter d, and max degree Delta on n vertices with the fewest edges? – utdiscant May 29 '11 at 18:30
@utdiscant Yes, exactly. And in case there would be no results on the general problem, I'll be thankful just for the case d = 2, Delta = 4. – Skiminok May 29 '11 at 18:35
For the minimal number of edges, if you require at least one vertex have degree $\Delta$, how about a star with $\Delta$ points? – Ross Millikan Aug 31 '11 at 16:00
What's $K3*C5$? – Chris Godsil Oct 1 '11 at 1:32
@Chris, $K_3$ is a triangle, $C_5$ is a cycle of length 5, and for the product, take three little pentagons, and join each vertex in each pentagon to the corresponding vertex in each of the other pentagons. – Gerry Myerson Feb 27 '12 at 23:37

This is very similar to the graph diameter problem. You'll probably find your answer in the realm of Distance Regular Graphs, since minimal/maximal solutions in graph theory tend to have a lot of symmetry.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.