Star extremal circulant graphs

被引:18
|
作者
Lih, KW [1 ]
Liu, DDF
Zhu, XD
机构
[1] Acad Sinica, Inst Math, Taipei 11529, Taiwan
[2] Calif State Univ Los Angeles, Dept Math & Comp Sci, Los Angeles, CA 90032 USA
[3] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 80424, Taiwan
关键词
circular chromatic number; fractional chromatic number; circulant graph; distance graph; star extremal graph; independence ratio;
D O I
10.1137/S0895480198342838
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A graph is called star extremal if its fractional chromatic number is equal to its circular chromatic number (also known as the star chromatic number). We prove that members of a certain family of circulant graphs are star extremal. The result generalizes some known theorems of Sidorenko [Discrete Math., 91 (1991), pp. 215-217] and Gao and Zhu [Discrete Math., 152 (1996), pp. 147-156]. We show relations between circulant graphs and distance graphs and discuss their star extremality. Furthermore, we give counterexamples to two conjectures of Collins [SIAM J. Discrete Math., 11 (1998), pp. 330-339] on asymptotic independence ratios of circulant graphs.
引用
收藏
页码:491 / 499
页数:9
相关论文
共 50 条
  • [31] Betti Numbers of Some Circulant Graphs
    Mohsen Abdi Makvand
    Amir Mousivand
    Czechoslovak Mathematical Journal, 2019, 69 : 593 - 607
  • [32] COHEN-MACAULAY CIRCULANT GRAPHS
    Vander Meulen, Kevin N.
    Van Tuyl, Adam
    Watt, Catriona
    COMMUNICATIONS IN ALGEBRA, 2014, 42 (05) : 1896 - 1910
  • [33] On the broadcast independence number of circulant graphs
    Laouar, Abdelamin
    Bouchemakh, Isma
    Sopena, Eric
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2024, 16 (05)
  • [34] The game of Cops and Robber on circulant graphs
    Fitzpatrick, Shannon L.
    Larkin, John Paul
    DISCRETE APPLIED MATHEMATICS, 2017, 225 : 64 - 73
  • [35] Well-covered circulant graphs
    Brown, Jason
    Hoshino, Richard
    DISCRETE MATHEMATICS, 2011, 311 (04) : 244 - 251
  • [36] The number of rooted forests in circulant graphs
    Grunwald, Lilya A.
    Mednykh, Ilya
    ARS MATHEMATICA CONTEMPORANEA, 2022, 22 (04)
  • [37] On the partition dimension of directed circulant graphs
    Maritz, Elizabeth C. M.
    Vetrik, Tomas
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2023, 26 (01) : 1 - 10
  • [38] On Hamilton decompositions of infinite circulant graphs
    Bryant, Darryn
    Herke, Sarada
    Maenhaut, Barbara
    Webb, Bridget S.
    JOURNAL OF GRAPH THEORY, 2018, 88 (03) : 434 - 448
  • [39] Spanning trees in directed circulant graphs and cycle power graphs
    Justine Louis
    Monatshefte für Mathematik, 2017, 182 : 51 - 63
  • [40] Embedding of circulant graphs and generalized Petersen graphs on projective plane
    Yan Yang
    Yanpei Liu
    Frontiers of Mathematics in China, 2015, 10 : 209 - 220