On bipartite graphs of defect at most 4

We consider the bipartite version of the degree/diameter problem, namely, given natural numbers Δ<2 and D<2, find the maximum number N b(Δ,D) of vertices in a bipartite graph of maximum degree Δ and diameter D. In this context, the Moore bipartite bound M b(Δ,D) represents an upper bound for Nb(Δ,D). Bipartite graphs of maximum degree Δ, diameter D and order M b(Δ,D)called Moore bipartite graphshave turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree Δ<2, diameter D<2 and order Mb(Δ,D)- with small >0, that is, bipartite (Δ,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 and D<3, they may only exist for D=3. However, when >2 bipartite (Δ,D,-)-graphs represent a wide unexplored area. The main results of the paper include several necessary conditions for the existence of bipartite (Δ,D,-4)-graphs; the complete catalogue of bipartite (3,D,-)-graphs with D<2 and 0≤≤4; the complete catalogue of bipartite (Δ,D,-)-graphs with Δ<2, 5≤D≤187 (D≠6) and 0≤≤4; a proof of the non-existence of all bipartite (Δ,D,-4)-graphs with Δ<3 and odd D<5. Finally, we conjecture that there are no bipartite graphs of defect 4 for Δ<3 and D<5, and comment on some implications of our results for the upper bounds of Nb(Δ,D).