On large bipartite graphs of diameter 3

الأصل · EN

We consider the bipartite version of the degree/diameter problem, namely, given natural numbers d≥2 and D≥2, find the maximum number ᵇ(d,D) of vertices in a bipartite graph of maximum degree d and diameter D. In this context, the bipartite Moore bound ᵇ(d,D) represents a general upper bound for ᵇ(d,D). Bipartite graphs of order ᵇ(d,D) are very rare, and determining ᵇ(d,D) still remains an open problem for most (d,D) pairs. This paper is a follow-up to our earlier paper FPV12, where a study on bipartite (d,D,-4)-graphs (that is, bipartite graphs of order ᵇ(d,D)-4) was carried out. Here we first present some structural properties of bipartite (d,3,-4)-graphs, and later prove there are no bipartite (7,3,-4)-graphs. This result implies that the known bipartite (7,3,-6)-graph is optimal, and therefore ᵇ(7,3)=80. Our approach also bears a proof of the uniqueness of the known bipartite (5,3,-4)-graph, and the non-existence of bipartite (6,3,-4)-graphs. In addition, we discover three new largest known bipartite (and also vertex-transitive) graphs of degree 11, diameter 3 and order 190, result which improves by 4 vertices the previous lower bound for ᵇ(11,3).