Let $G$ be a $r$-regular graph with $n$-vertices with diameter $2$. I want to find a good bound for $n$ in terms of $r$.

First I observe that it can be said that $n\leq r^2+r$. There are at most $r^2$ vertex which is not adjacent to a vertex. Thus, we get $n-r\leq r^2$ and result follows.

We may also assume that for every non-adjecent two vertex $v_1,v_2$ there is a unique $v_3$ that the path $v_1v_3v_2$ has length $2$. Any reference is welcome. If it is easy to do, any hint or solution is also welcome.

  • $\begingroup$ Did you really mean dimension or was that a typo for diameter? $\endgroup$ – bof May 25 '17 at 21:49
  • $\begingroup$ Why can you assume that "for every non-adjacent two vertex $v_1,v_2$ there is a unique $v_3$ that the path $v_1v_3v_2$ has length $2$"? How does that work out when $r=2$ and $n=4$? $\endgroup$ – bof May 25 '17 at 21:56
  • $\begingroup$ @bof: Yes, I mean diameter. you are right $r^2+r+1$. I also write this extra assumption that it can be also assumed if it causes better bound. $\endgroup$ – mesel May 25 '17 at 22:06

Suppose $G$ is $r$-regular with diameter two. A vertex $u$ has $r$ neighbours, and each of these neighbours is adjacent to at most $r-1$ vertices at distance two from $u$. So the number of vertices of the graph is at most $$ 1+ r + r(r-1) = r^2+1. $$ This bound, a special case of the Moore bound, can only be tight if $r\in\{2,3,7, 57\}$ - famous result due to Hoffman and Singleton. For 2, 3, 7 there unique examples: respectively $C_5$, the Petersen graph and the Hoffman-Singleton graph on 50 vertices. The existence of 57-regular graph of diameter two on 3250 vertices is a very famous open problem.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much. Let me ask you that under the additional assumption which i mentioned, do you see better bound ? $\endgroup$ – mesel May 25 '17 at 22:28
  • $\begingroup$ Ok, I guess I see. The extra assumption force that $n$ is exactly $r^2+1$. In some how I had expected a linear bound, that is why I did not try to improve the polynomial bound. $\endgroup$ – mesel May 25 '17 at 22:33
  • $\begingroup$ @mesel: if $|V(G)|=1+r^2$, then it follows that any two vertices in the graph at distance two have a unique common neighbour (and the graph has girth five). So the additional assumption has no effect. $\endgroup$ – Chris Godsil May 25 '17 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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