On bipartite graphs of defect at most 4

We consider the bipartite version of the degree/diameter problem  , namely, given natural numbers Δ≥2Δ≥2 and D≥2D≥2, find the maximum number Nb(Δ,D) of vertices in a bipartite graph of maximum degree ΔΔ and diameter DD. In this context, the Moore bipartite bound Mb(Δ,D) represents an upper bound for Nb(Δ,D).Bipartite graphs of maximum degree ΔΔ, diameter DD and order Mb(Δ,D)–called Moore bipartite graphs  –have turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Δ≥2Δ≥2, diameter D≥2D≥2 and order Mb(Δ,D)−ϵ with small ϵ>0ϵ>0, that is, bipartite (Δ,D,−ϵ)(Δ,D,−ϵ)-graphs. The parameter ϵϵ is called the defect.This paper considers bipartite graphs of defect at most 4, and presents all the known such graphs. Bipartite graphs of defect 2 have been studied in the past; if Δ≥3Δ≥3 and D≥3D≥3, they may only exist for D=3D=3. However, when ϵ>2ϵ>2 bipartite (Δ,D,−ϵ)(Δ,D,−ϵ)-graphs represent a wide unexplored area.The main results of the paper include several necessary conditions for the existence of bipartite (Δ,D,−4)(Δ,D,−4)-graphs; the complete catalogue of bipartite (3,D,−ϵ)(3,D,−ϵ)-graphs with D≥2D≥2 and 0≤ϵ≤40≤ϵ≤4; the complete catalogue of bipartite (Δ,D,−ϵ)(Δ,D,−ϵ)-graphs with Δ≥2Δ≥2, 5≤D≤1875≤D≤187 (D≠6D≠6) and 0≤ϵ≤40≤ϵ≤4; a proof of the non-existence of all bipartite (Δ,D,−4)(Δ,D,−4)-graphs with Δ≥3Δ≥3 and odd D≥5D≥5.Finally, we conjecture that there are no bipartite graphs of defect 4 for Δ≥3Δ≥3 and D≥5D≥5, and comment on some implications of our results for the upper bounds of Nb(Δ,D).

► We study bipartite graphs of defect ≤ 4 (graphs missing the Moore bipartite bound by at most 4). ► We present all such known graphs and include several necessary conditions for their existence. ► Complete catalogues of several families of bipartite graphs of defect at most 4 are also provided. ► We conjecture that there are no bipartite graphs of defect 4 for maximum degrees ≥ 3 and diameters ≥ 5.