Girth 5 graphs from relative difference sets

被引：15

作者：

Jorgensen, LK ^{[1
]}

机构：

[1] Univ Aalborg, Dept Math Sci, DK-9220 Aalborg, Denmark

来源：

DISCRETE MATHEMATICS | 2005年 / 293卷 / 1-3期

关键词：

cage; girth; Cayley graph; relative difference set;

D O I：

10.1016/j.disc.2004.08.029

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the problem of construction of graphs with given degree k and girth 5 and as few vertices as possible. We give a construction of a family of girth 5 graphs based on relative difference sets. This family contains the smallest known graph of degree 8 and girth 5 which was constructed by Royle, four of the known cages including the Hoffman-Singleton graph, some graphs constructed by Exoo and some new smallest known graphs. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：177 / 184

页数：8

共 50 条

[21] A group extensions approach to relative difference sets [J].

Galati, JC .

JOURNAL OF COMBINATORIAL DESIGNS, 2004, 12 (04) :279-298

[22] Two generalized constructions of relative difference sets [J].

Hou, XD ;

Sehgal, SK .

JOURNAL OF ALGEBRAIC COMBINATORICS, 2000, 12 (02) :145-153

[23] Two Generalized Constructions of Relative Difference Sets [J].

Xiang-Dong Hou ;

Surinder K. Sehgal .

Journal of Algebraic Combinatorics, 2000, 12 :145-153

[24] On tetravalent half-arc-transitive graphs of girth 5 [J].

Antoncic, Iva ;

Sparl, Primoz .

DISCRETE MATHEMATICS, 2023, 346 (10)

[25] On 2-distance coloring of plane graphs with girth 5 [J].

Dong, Wei ;

Lin, Wensong .

DISCRETE APPLIED MATHEMATICS, 2017, 217 :495-505

[26] 2-Distance coloring of planar graphs with girth 5 [J].

Dong, Wei ;

Xu, Baogang .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (04) :1302-1322

[27] Girth and ?-choosability of graphs [J].

Gu, Yangyan ;

Zhu, Xuding .

JOURNAL OF GRAPH THEORY, 2023, 103 (03) :493-501

[28] Girth of pancake graphs [J].

Compeau, Phillip E. C. .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (15) :1641-1645

[29] Acyclic edge coloring of planar graphs with girth at least 5 [J].

Hou, Jianfeng ;

Wang, Weitao ;

Zhang, Xiaoran .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) :2958-2967

[30] LIST INJECTIVE COLORING OF PLANAR GRAPHS WITH GIRTH g >= 5 [J].

Bu, Yuehua ;

Yang, Sheng .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (01)

← 1 2 3 4 5 →