On graphs of defect at most 2

In this paper we consider the degree/diameter problem  , namely, given natural numbers Δ≥2Δ≥2 and D≥1D≥1, find the maximum number N(Δ,D) of vertices in a graph of maximum degree ΔΔ and diameter DD. In this context, the Moore bound M(Δ,D) represents an upper bound for N(Δ,D).Graphs of maximum degree ΔΔ, diameter DD 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≥1D≥1 and order M(Δ,D)−ϵ with small ϵ>0ϵ>0, that is, (Δ,D,−ϵ)(Δ,D,−ϵ)-graphs. The parameter ϵϵ is called the defect.Graphs of defect 11 exist only for Δ=2Δ=2. When ϵ>1ϵ>1, (Δ,D,−ϵ)(Δ,D,−ϵ)-graphs represent a wide unexplored area. This paper focuses on graphs of defect 22. Building on the approaches developed in Feria-Purón 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≥4D≥4 is 2D2D. Second, and most important, we prove the non-existence of (Δ,D,−2)(Δ,D,−2)-graphs with even Δ≥4Δ≥4 and D≥4D≥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≥2D≥2 and 0≤ϵ≤20≤ϵ≤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≥2D≥2 and 0≤ϵ≤20≤ϵ≤2 Jørgensen (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≥4D≥4, and the non-existence of (Δ,D,−2)(Δ,D,−2)-graphs with odd Δ≥5Δ≥5 and D≥5D≥5 such that Δ≡0,2(modD).Finally, we conjecture that there are no (Δ,D,−2)(Δ,D,−2)-graphs with Δ≥4Δ≥4 and D≥4D≥4, and comment on some implications of our results for the upper bounds of N(Δ,D).