Graphs of Diameter two Without Small Cycles

Abstract

It is known that triangle-free graphs of diameter $2$ are just maximal triangle-free graphs. Kantor ([5]) showed that if $G$ is a triangle-free and $4$-cycle free graph of diameter $2$, then $G$ is either a star or a Moore graph of diameter $2$; if $G$ is a $4$-cycle free graph of diameter $2$ with at least one triangle, then $G$ is either a star-like graph or a polarity graph (defined from a finite projective plane with polarities) of order $r^2+r+1$ for some positive integer $r$ (or $P_r$-\emph{graph} for short). We study, by purely graph theoretical means, the structure of $P_r$-graphs and construct $P_r$-graphs for small values of $r$. Further, we characterize graphs of diameter $2$ without $5$-cycles and $6$-cycles, respectively. In general, one can characterize $C_k$-free graphs of diameter $2$ with $k>6$ with a similar approach.