Menu
The Moore upper bound for the order \( n(\Delta, 2) \) of graphs with maximum degree \( \Delta \) and diameter two is \( n(\Delta, 2) < \Delta^2 + 1 \). The only general lower bound for vertex symmetric graphs is \( n_{vt}(\Delta, 2) \geq \left\lfloor \frac{\Delta + 2}{2} \right\rfloor \left\lceil \frac{\Delta + 2}{2} \right\rceil \). Recently, a construction of vertex transitive graphs of diameter two, based on voltage graphs, with order \( \frac{8}{9} \left( \Delta + \frac{1}{2} \right)^2 \) has been given in [5] for \( \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} (\Delta + 1)^2 \), where \( \Delta = 2q – 1 \). For \( q = 4 \), we obtain a vertex transitive graph of degree 6 and order 32.