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 条
  • [41] On the girth of Hamiltonian weakly pancyclic graphs
    Bollobas, B
    Thomason, A
    JOURNAL OF GRAPH THEORY, 1997, 26 (03) : 165 - 173
  • [42] Small regular graphs of girth 7
    Abreu, M.
    Araujo-Pardo, G.
    Balbuena, C.
    Labbate, D.
    Salas, J.
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (03)
  • [43] Token Sliding on Graphs of Girth Five
    Bartier, Valentin
    Bousquet, Nicolas
    Hanna, Jihad
    Mouawad, Amer E.
    Siebertz, Sebastian
    ALGORITHMICA, 2024, 86 (02) : 638 - 655
  • [44] Token Sliding on Graphs of Girth Five
    Valentin Bartier
    Nicolas Bousquet
    Jihad Hanna
    Amer E. Mouawad
    Sebastian Siebertz
    Algorithmica, 2024, 86 : 638 - 655
  • [45] Cycles and Girth in Pebble Assignment Graphs
    Fiorini, E.
    Johnston, G.
    Lind, M.
    Woldar, A.
    Wong, T. W. H.
    GRAPHS AND COMBINATORICS, 2022, 38 (05)
  • [46] ON COLOURING ORIENTED GRAPHS OF LARGE GIRTH
    Kayll, P. Mark
    Morris, Michael
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2023, 18 (02) : 234 - 243
  • [47] Topological minors in graphs of large girth
    Kühn, D
    Osthus, D
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 364 - 380
  • [48] The size of bipartite graphs with a given girth
    Hoory, S
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (02) : 215 - 220
  • [49] On Tensor Product of Graphs, Girth and Triangles
    Patil, H. P.
    Raja, V.
    IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2015, 10 (01): : 139 - 147
  • [50] Secret sharing on large girth graphs
    László Csirmaz
    Péter Ligeti
    Cryptography and Communications, 2019, 11 : 399 - 410