On graphs of defect at most 2
In this paper we consider the degree/diameter problem , namely, given natural numbers ??2 ? ? 2 and D?1 D ? 1 , find the maximum number N ( ? , D ) of vertices in a graph of maximum degree ? ? and diameter D D . In this context, the Moore bound M ( ? , D ) represents an upper bound for N ( ? , D ) . Graphs of maximum degree ? ? , diameter D D and order M ( ? , D ) , called Moore graphs , have turned out to be very rare. Therefore, it is very interesting to investigate graphs of maximum degree ??2 ? ? 2 , diameter D?1 D ? 1 and order M ( ? , D ) ? ? with small ?>0 ? > 0 , that is, (?,D,??) ( ? , D , ? ? ) -graphs. The parameter ? ? is called the defect. Graphs of defect 1 1 exist only for ?=2 ? = 2 . When ?>1 ? > 1 , (?,D,??) ( ? , D , ? ? ) -graphs represent a wide unexplored area. This paper focuses on graphs of defect 2 2 . Building on the approaches developed in Feria-Purn and Pineda-Villavicencio (2010) [11] we obtain several new important results on this family of graphs. First, we prove that the girth of a (?,D,?2) ( ? , D , ? 2 ) -graph with ??4 ? ? 4 and D?4 D ? 4 is 2D 2 D . Second, and most important, we prove the non-existence of (?,D,?2) ( ? , D , ? 2 ) -graphs with even ??4 ? ? 4 and D?4 D ? 4 ; this outcome, together with a proof on the non-existence of (4,3,?2) ( 4 , 3 , ? 2 ) -graphs (also provided in the paper), allows us to complete the catalogue of (4,D,??) ( 4 , D , ? ? ) -graphs with D?2 D ? 2 and 0???2 0 ? ? ? 2 . Such a catalogue is only the second census of (?,D,?2) ( ? , D , ? 2 ) -graphs known at present, the first being that of (3,D,??) ( 3 , D , ? ? ) -graphs with D?2 D ? 2 and 0???2 0 ? ? ? 2 Jrgensen (1992) [14]. Other results of this paper include necessary conditions for the existence of (?,D,?2) ( ? , D , ? 2 ) -graphs with odd ??5 ? ? 5 and D?4 D ? 4 , and the non-existence of (?,D,?2) ( ? , D , ? 2 ) -graphs with odd ??5 ? ? 5 and D?5 D ? 5 such that ? ? 0 , 2 ( mod D ) . Finally, we conjecture that there are no (?,D,?2) ( ? , D , ? 2 ) -graphs with ??4 ? ? 4 and D?4 D ? 4 , and comment on some implications of our results for the upper bounds of N ( ? , D ) .
defect degree/diameter problem moore bound moore graph repeat