On bipartite graphs of defect at most 4

详细信息    查看全文

• 作者：Ramiro Feria-Puró ; n^a ;   ; ^{ramiro.feria.puron@gmail.com} ; Guillermo Pineda-Villavicencio^b ;   ; ^{work@guillermo.com.au}
• 关键词：Moore bipartite bound ; Moore bipartite graph ; Degree/diameter problem for bipartite graphs ; Defect ; Repeat
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：January 2012
• 年：2012
• 卷：160
• 期：1-2
• 页码：140-154
• 全文大小：669 K

文摘

We consider the bipartite version of the degree/diameter problem, namely, given natural numbers and , find the maximum number of vertices in a bipartite graph of maximum degree and diameter . In this context, the Moore bipartite bound represents an upper bound for .

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 .