Girth 5 Graphs from Elliptic Semiplanes

被引:7
|
作者
Funk, M. [1 ]
机构
[1] Univ Basilicata, Dipartimento Matemat Informat, Viale Ateneo Lucano, I-85100 Potenza, Italy
来源
NOTE DI MATEMATICA | 2009年 / 29卷
关键词
(k; 5)-cages; girth; 5; graphs; elliptic semiplanes; Hughes planes;
D O I
10.1285/i15900932v29n1supplp91
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For 3 <= k <= 20 with k not equal 4, 8, 12, all the smallest currently known k-regular graphs of girth 5 have the same orders as the girth 5 graphs obtained by the following construction: take a (not necessarily Desarguesian) elliptic semiplane S of order n - 1 where n = k - r for some r >= 1; the Levi graph Gamma(S) of S is an n-regular graph of girth 6; parallel classes of S induce co-cliques in Gamma(S), some of which are eventually deleted; the remaining co-cliques are amalgamated with suitable r-regular graphs of girth at least 5. For k > 20, this construction yields some new instances underbidding the smallest orders known so far.
引用
收藏
页码:91 / 113
页数:23
相关论文
共 50 条
  • [1] Regular graphs of girth 5 from elliptic semiplanes of type C
    Abajo, E.
    Bendala, M.
    DISCRETE MATHEMATICS, 2021, 344 (06)
  • [2] New small regular graphs of girth 5
    Abajo, E.
    Araujo-Pardo, G.
    Balbuena, C.
    Bendala, M.
    DISCRETE MATHEMATICS, 2017, 340 (08) : 1878 - 1888
  • [3] Girth 5 graphs from relative difference sets
    Jorgensen, LK
    DISCRETE MATHEMATICS, 2005, 293 (1-3) : 177 - 184
  • [4] Families of small regular graphs of girth 5
    Abreu, M.
    Araujo-Pardo, G.
    Balbuena, C.
    Labbate, D.
    DISCRETE MATHEMATICS, 2012, 312 (18) : 2832 - 2842
  • [5] Injective coloring of planar graphs with girth 5
    Bu, Yuehua
    Ye, Piaopiao
    FRONTIERS OF MATHEMATICS IN CHINA, 2022, 17 (03) : 473 - 484
  • [6] Injective coloring of plane graphs with girth 5
    Dong, Wei
    Lin, Wensong
    DISCRETE MATHEMATICS, 2014, 315 : 120 - 127
  • [7] Injective coloring of planar graphs with girth 5
    Yuehua Bu
    Piaopiao Ye
    Frontiers of Mathematics in China, 2022, 17 : 473 - 484
  • [8] Improving bounds on the order of regular graphs of girth 5
    Abajo, E.
    Balbuena, C.
    Bendala, M.
    Marcote, X.
    DISCRETE MATHEMATICS, 2019, 342 (10) : 2900 - 2910
  • [9] The Erdos-Sos conjecture for graphs of girth 5
    Brandt, S
    Dobson, E
    DISCRETE MATHEMATICS, 1996, 150 (1-3) : 411 - 414
  • [10] Total Domination in Graphs with Given Girth
    Michael A. Henning
    Anders Yeo
    Graphs and Combinatorics, 2008, 24 : 333 - 348