1
$\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 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.

  • 0
    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?2011-05-29
  • 0
    @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.2011-05-29
  • 2
    For the minimal number of edges, if you require at least one vertex have degree $\Delta$, how about a star with $\Delta$ points?2011-08-31
  • 0
    What's $K3*C5$?2011-10-01
  • 1
    @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.2012-02-27
  • 0
    $K_3 * C_5$ has diameter 3, not 2.2018-11-19

1 Answers 1