Bipartite graphs of maximum degree , diameter and order ¨Ccalled Moore bipartite graphs¨Chave turned out to be very rare. Therefore, it is very interesting to investigate bipartite graphs of maximum degree , diameter and order with small , that is, bipartite -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 and , they may only exist for . However, when bipartite -graphs represent a wide unexplored area.
The main results of the paper include several necessary conditions for the existence of bipartite -graphs; the complete catalogue of bipartite -graphs with and ; the complete catalogue of bipartite -graphs with , () and ; a proof of the non-existence of all bipartite -graphs with and odd .
Finally, we conjecture that there are no bipartite graphs of defect 4 for and , and comment on some implications of our results for the upper bounds of .