# $r$-regular graph with diameter $2$

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.

• Did you really mean dimension or was that a typo for diameter? – bof May 25 '17 at 21:49
• 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$? – bof May 25 '17 at 21:56
• @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. – 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.
• 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. – mesel May 25 '17 at 22:33
• @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. – Chris Godsil May 25 '17 at 23:37