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.

Improve this question
$\endgroup$
3
  • $\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, 2011 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, 2011 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, 2013 at 17:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.