On large bipartite graphs of diameter 3

We consider the bipartite version of the <i>degree/diameter problem</i>, namely, given natural numbers <b>d≥2</b> and <b>D≥2</b>, find the maximum number _{Nᵇ(<i>d</i>, D)} of vertices in a bipartite graph of maximum degree <b>d</b> and diameter <b>D</b>. In this context, the bipartite Moore bound _{Mᵇ(<i>d</i>,D)} represents a general upper bound for _{Nᵇ(<i>d</i>,D)}. Bipartite graphs of order _{Mᵇ(<i>d</i>,D)} are very rare, and determining _{Nb(<i>d</i>,D)} still remains an open problem for most <b>(d,D)</b> pairs. This paper is a follow-up of our earlier paper (Feria-Purón and Pineda-Villavicencio, 2012 [5]), where a study on bipartite <b>(d,D,−4)</b>-graphs (that is, bipartite graphs of order _{Mb(<i>d</i>,D)−4)} was carried out. Here we first present some structural properties of bipartite <b>(d,3,−4)</b>-graphs, and later prove that there are no bipartite <b>(7,3,−4)</b>-graphs. This result implies that the known bipartite <b>(7,3,−6)</b>-graph is optimal, and therefore _Nᵇ(7,3)=80. We dub this graph the Hafner–Loz graph after its first discoverers Paul Hafner and Eyal Loz. The approach here presented also provides a proof of the uniqueness of the known bipartite <b>(5,3,−4)</b>-graph, and the non-existence of bipartite <b>(6,3,−4)</b>-graphs. In addition, we discover at least one new largest known bipartite–and also vertex-transitive–graph of degree 11, diameter 3 and order 190, a result which improves by four vertices the previous lower bound for <sub>Nᵇ(11,3)