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 条
  • [31] Extremal Graphs with Girth Nine
    Zhang Rui
    Sun Yongqi
    Wu Yali
    ARS COMBINATORIA, 2019, 142 : 345 - 356
  • [32] On the Girth of Random Cayley Graphs
    Gamburd, A.
    Hoory, S.
    Shahshahani, M.
    Shalev, A.
    Virag, B.
    RANDOM STRUCTURES & ALGORITHMS, 2009, 35 (01) : 100 - 117
  • [33] Girth and Total Domination in Graphs
    Henning, Michael A.
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 199 - 214
  • [34] Proximity, remoteness and girth in graphs
    Aouchiche, M.
    Hansen, P.
    DISCRETE APPLIED MATHEMATICS, 2017, 222 : 31 - 39
  • [35] Constant Girth Approximation for Directed Graphs in Subquadratic Time
    Chechik, Shiri
    Liu, Yang P.
    Rotem, Omer
    Sidford, Aaron
    PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, : 1010 - 1023
  • [36] On minimum girth of graphs reconstructible from metric balls of their vertices
    Levenshtein, Vladimir I.
    2006 IEEE International Symposium on Information Theory, Vols 1-6, Proceedings, 2006, : 2488 - 2490
  • [37] An (F3, F5)-partition of planar graphs with girth at least 5
    Chen, Min
    Raspaud, Andre
    Wang, Weifan
    Yu, Weiqiang
    DISCRETE MATHEMATICS, 2023, 346 (02)
  • [38] An improved bound on 2-distance coloring plane graphs with girth 5
    Dong, Wei
    Lin, Wensong
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (02) : 645 - 655
  • [39] An improved bound on 2-distance coloring plane graphs with girth 5
    Wei Dong
    Wensong Lin
    Journal of Combinatorial Optimization, 2016, 32 : 645 - 655
  • [40] Locating-Dominating Sets and Identifying Codes in Graphs of Girth at least 5
    Balbuena, Camino
    Foucaud, Florent
    Hansberg, Adriana
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02)