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 条
[41]   LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH [J].
Hudak, Peter ;
Macekova, Maria ;
Madaras, Tomas ;
Siroczki, Pavol .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) :227-238
[42]   List injective coloring of planar graphs with girth 5, 6, 8 [J].
Bu, Yuehua ;
Lu, Kai .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1367-1377
[43]   A new upper bound for the spectral radius of graphs with girth at least 5 [J].
Lu, M ;
Liu, HQ ;
Tian, F .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 414 (2-3) :512-516
[44]   On the Randic index and girth of graphs [J].
Liang, Meili ;
Liu, Bolian .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (1-2) :212-216
[45]   Girth and Total Domination in Graphs [J].
Michael A. Henning ;
Anders Yeo .
Graphs and Combinatorics, 2012, 28 :199-214
[46]   Girth-regular graphs [J].
Potocnik, Primoz ;
Vidali, Janos .
ARS MATHEMATICA CONTEMPORANEA, 2019, 17 (02) :349-368
[47]   On The Harmonic Index and The Girth for Graphs [J].
Zhong, Lingping .
ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 2013, 16 (04) :253-260
[48]   Proximity, remoteness and girth in graphs [J].
Aouchiche, M. ;
Hansen, P. .
DISCRETE APPLIED MATHEMATICS, 2017, 222 :31-39
[49]   Girth and Total Domination in Graphs [J].
Henning, Michael A. ;
Yeo, Anders .
GRAPHS AND COMBINATORICS, 2012, 28 (02) :199-214
[50]   On the Girth of Random Cayley Graphs [J].
Gamburd, A. ;
Hoory, S. ;
Shahshahani, M. ;
Shalev, A. ;
Virag, B. .
RANDOM STRUCTURES & ALGORITHMS, 2009, 35 (01) :100-117
12345