A family of regular graphs of girth 5

被引：8

作者：

Abreu, M. ^{[1
]}

Funk, M. ^{[1
]}

Labbate, D. ^{[2
]}

Napolitano, V. ^{[1
]}

机构：

[1] Univ Basilicata, Dipartimento Matemat, Viale Dell Ateneo Lucano, I-85100 Potenza, Italy

[2] Politecn Bari, Dipartimento Matemat, I-70125 Bari, Italy

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 10期

关键词：

regular graphs; cages;

D O I：

10.1016/j.disc.2007.04.031

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p(m) + 2)-regular graphs of girth five and order 2p(2m), where p >= 5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f (k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f (k), k >= 16. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：1810 / 1815

页数：6