3
$\begingroup$

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 vertexes 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 a community for any advices or links to researches. Thank you for any assistance.

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ I would start by taking Delta as small as possible and constructing a diameter 2 graph with small Delta, and then adding vertices with Delta+1 edges to set up for making the diameter between newly added vertices small. THis may be better than brute force, but not by much. Good Luck. Gerhard "Ask Me About System Design" Paseman, 2011.05.29 $\endgroup$ – Gerhard Paseman May 29 '11 at 18:33
  • $\begingroup$ My impression after thinking about this for a while is that if you really want to be sure you've found one of the graphs fulfilling the minimal number of edges condition, you pretty much need to use brute force. You might be able to prove that amongst the graphs with minimal number of edges fulfilling all the conditions, when V-1 is at least delta, that there is always some graph with a vertex of maximal allowable degree. This might cut down on the brute force and allow you to handle V between 9 and 14 to resolve the case you're interested in. $\endgroup$ – Orange May 30 '11 at 8:32
  • $\begingroup$ This sounds like an "irregular edge-Moore graph", but such graphs seem not to have been studied... $\endgroup$ – Felix Goldberg Jan 22 '13 at 17:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.