Examples of diameter-2 graphs with no triangle or $K_{2,t}$

Abstract

For each $t\ge 1$ let $W_t$ denote the class of graphs other than stars that have diameter $2$ and contain neither a triangle nor a $K_{2,t}$. The famous Hoffman--Singleton Theorem implies that $W_2$ is finite. Recently Wood suggested the study of $W_t$ for $t>2$ and conjectured that $W_t$ is finite for all $t\ge 2$. In this note we show that (1) $W_3$ is infinite, (2) $W_5$ contains infinitely many regular graphs, and (3) $W_7$ contains infinitely many Cayley graphs. Our $W_3$ and $W_5$ examples are based on so-called crooked graphs, first constructed by de Caen, Mathon, and Moorhouse. Our $W_7$ examples are Cayley graphs with vertex set ${\mathbb{F}}_p^2$ for prime $p\equiv 11(\mathrm{mod}12)$.

8 pages