On large bipartite graphs of diameter 3

详细信息    查看全文

• 作者：Ramiro Feria-Puró ; n^a ; ^{Ramiro.Feria-Puron@uon.edu.au} ; Mirka Miller^a ; ^b ; ^c ; ^d ; ^{mirka.miller@newcastle.edu.au} ; Guillermo Pineda-Villavicencio^e ; ^{work@guillermo.com.au}
• 关键词：Degree/diameter problem for bipartite graphs ; Bipartite Moore bound ; Large bipartite graphs ; Defect
• 刊名：Discrete Mathematics
• 出版年：2013
• 出版时间：28 February, 2013
• 年：2013
• 卷：313
• 期：4
• 页码：381-390
• 全文大小：296 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 bipartite Moore bound represents a general upper bound for . Bipartite graphs of order are very rare, and determining still remains an open problem for most pairs.

This paper is a follow-up of our earlier paper (Feria-Pur¨®n and Pineda-Villavicencio, 2012 ), where a study on bipartite -graphs (that is, bipartite graphs of order ) was carried out. Here we first present some structural properties of bipartite -graphs, and later prove that there are no bipartite -graphs. This result implies that the known bipartite -graph is optimal, and therefore . 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 -graph, and the non-existence of bipartite -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 .