On Graphs of Maximum Degree 3 and Defect 4

Abstract

It is well known that apart from the Petersen graph, there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and $\delta$ vertices less than the Moore bound, where $\delta$ is odd. Additionally, it is known that there exist only three graphs of maximum degree 3 and 2 vertices less than the Moore bound. In this paper, we consider graphs of maximum degree 3, diameter $D\ge 2$, and 4 vertices less than the Moore bound, denoted as $(3,D,4)$-graphs. We obtain all non-isomorphic $(3,D,4)$-graphs for $D=2$. Furthermore, for any diameter $D$, we consider the girth of $(3,D,4)$-graphs. By a counting argument, it is easy to see that the girth is at least $2D–2$. The main contribution of this paper is that we prove that the girth of a $(3,D,4)$-graph is at least $2D–1$. Finally, for $D>4$, we conjecture that the girth of a $(3,D,4)$-graph is $2D$.