A Geometric Construction of Large Vertex Transitive Graphs of Diameter Two

Abstract

The Moore upper bound for the order $n(\mathrm{\Delta },2)$ of graphs with maximum degree $\mathrm{\Delta }$ and diameter two is $n(\mathrm{\Delta },2)<{\mathrm{\Delta }}^2+1$. The only general lower bound for vertex symmetric graphs is $n_{vt}(\mathrm{\Delta },2)\ge \lfloor \frac{\mathrm{\Delta }+2}{2}\rfloor \lceil \frac{\mathrm{\Delta }+2}{2}\rceil$. Recently, a construction of vertex transitive graphs of diameter two, based on voltage graphs, with order $\frac{8}{9}{(\mathrm{\Delta }+\frac{1}{2})}^2$ has been given in [5] for $\mathrm{\Delta }=\frac{3q–1}{2}$ and $q$ a prime power congruent with 1 mod 4. We give an alternative geometric construction which provides vertex transitive graphs with the same parameters and, when $q$ is a prime power not congruent to 1 modulo 4, it gives vertex transitive graphs of diameter two and order $\frac{1}{2}(\mathrm{\Delta }+1{)}^2$, where $\mathrm{\Delta }=2q–1$. For $q=4$, we obtain a vertex transitive graph of degree 6 and order 32.