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 \geq 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 \).