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 条
  • [21] On magic and supermagic circulant graphs
    Semanicova, Andrea
    DISCRETE MATHEMATICS, 2006, 306 (18) : 2263 - 2269
  • [22] Resolvability in Subdivision Graph of Circulant Graphs
    Bokhary, Syed Ahtsham Ul Haq
    Wahid, Khola
    Ali, Usman
    Hilali, Shreefa O.
    Alhagyan, Mohammed
    Gargouri, Ameni
    SYMMETRY-BASEL, 2023, 15 (04):
  • [23] On the spectra of wreath products of circulant graphs
    Li, Xiaohong
    Zhang, Yongqin
    Wang, Jianfeng
    Li, Guang
    Huang, Da
    RICERCHE DI MATEMATICA, 2024, 73 (04) : 2173 - 2190
  • [24] Distance antimagic labeling of circulant graphs
    Sy, Syafrizal
    Simanjuntak, Rinovia
    Nadeak, Tamaro
    Sugeng, Kiki Ariyanti
    Tulus, Tulus
    AIMS MATHEMATICS, 2024, 9 (08): : 21177 - 21188
  • [25] The hyperbolicity constant of infinite circulant graphs
    Rodriguez, Jose M.
    Sigarreta, Jose M.
    OPEN MATHEMATICS, 2017, 15 : 800 - 814
  • [26] Perfect matching transitivity of circulant graphs
    Reiter, Isaac A.
    Zhou, Ju
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2022, 10 (02) : 541 - 552
  • [27] FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
    Thomson, Alison
    Zhou, Sawing
    JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2008, 85 (02) : 269 - 282
  • [28] Two families of circulant nut graphs
    Damnjanovic, Ivan
    FILOMAT, 2023, 37 (24) : 8331 - 8360
  • [29] Achromatic and Harmonious Colorings of Circulant Graphs
    Debski, Michal
    Lonc, Zbigniew
    Rzazewski, Pawel
    JOURNAL OF GRAPH THEORY, 2018, 87 (01) : 18 - 34
  • [30] Betti Numbers of Some Circulant Graphs
    Makvand, Mohsen Abdi
    Mousivand, Amir
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2019, 69 (03) : 593 - 607