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 条

[31] 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

[32] Girth of sparse graphs [J].

Bollobás, B ;

Szemerédi, E .

JOURNAL OF GRAPH THEORY, 2002, 39 (03) :194-200

[33] Describing short paths in plane graphs of girth at least 5 [J].

Jendrol', S. ;

Macekova, M. .

DISCRETE MATHEMATICS, 2015, 338 (02) :149-158

[34] Optimal unavoidable sets of types of 3-paths for planar graphs of given girth [J].

Jendrol', S. ;

Macekova, M. ;

Montassier, M. ;

Sotak, R. .

DISCRETE MATHEMATICS, 2016, 339 (02) :780-789

[35] Distances in graphs of girth 6 and generalised cages [J].

Alochukwu, Alex ;

Dankelmann, Peter .

DISCRETE APPLIED MATHEMATICS, 2021, 294 :125-137

[36] Cyclic relative difference sets and their p-ranks [J].

Chandler, DB ;

Xiang, Q .

DESIGNS CODES AND CRYPTOGRAPHY, 2003, 30 (03) :325-343

[37] Equivalence classes of central semiregular relative difference sets [J].

Horadam, KJ .

JOURNAL OF COMBINATORIAL DESIGNS, 2000, 8 (05) :330-346

[38] Relative difference sets in semidirect products with an amalgamated subgroup [J].

Galati, JC ;

LeBel, AC .

JOURNAL OF COMBINATORIAL DESIGNS, 2005, 13 (03) :211-221

[39] Cyclic Relative Difference Sets and their p-Ranks [J].

David B. Chandler ;

Qing Xiang .

Designs, Codes and Cryptography, 2003, 30 :325-343

[40] Triangles and Girth in Disk Graphs and Transmission Graphs [J].

Kaplan, Haim ;

Klost, Katharina ;

Mulzer, Wolfgang ;

Roditty, Liam ;

Seiferth, Paul ;

Sharir, Micha .

27TH ANNUAL EUROPEAN SYMPOSIUM ON ALGORITHMS (ESA 2019), 2019, 144

← 1 2 3 4 5 →