On graphs of maximum degree 3 and defect 4

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 δ vertices less than the Moore bound, where δ 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 ≥ 2 and 4 vertices legs 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.