Maximum genus, independence number and girth

被引：0
作者：
Yuanqiu H. [1 ]
Yanpei L. [2 ]
机构：
[1] Department of Mathematics, Normal University of Hunan, Changsha
[2] Department of Mathematics, Northern Jiaotong University, Beijing
来源：
Chinese Annals of Mathematics | 2000年 / 21卷 / 1期
关键词：
1991 MR Subject Classification: 05C; Betti deficiency; Girth; Independence number; Maximum genus; O157.5;
D O I：
10.1007/BF02731961
中图分类号：
学科分类号：
摘要：
It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible. © 1983 Shanghai Scientific & Technological Literature Publishing House.
引用
收藏
页码：77 / 82
页数：5
相关论文
共 50 条
  • [41] Matching Number, Independence Number, and Covering Vertex Number of Γ (Zn)
    AbuHijleh, Eman
    Abudayah, Mohammad
    Alomari, Omar
    Al-Ezeh, Hasan
    MATHEMATICS, 2019, 7 (01):
  • [42] The Game Coloring Number of Planar Graphs with a Specific Girth
    Keaitsuda Maneeruk Nakprasit
    Kittikorn Nakprasit
    Graphs and Combinatorics, 2018, 34 : 349 - 354
  • [43] The Wiener Index of Unicyclic Graphs with Girth and Matching Number
    Chen, Ya-Hong
    Zhang, Xiao-Dong
    ARS COMBINATORIA, 2012, 106 : 115 - 128
  • [44] The game coloring number of planar graphs with a given girth
    Sekiguchi, Yosuke
    DISCRETE MATHEMATICS, 2014, 330 : 11 - 16
  • [45] The Game Coloring Number of Planar Graphs with a Specific Girth
    Nakprasit, Keaitsuda Maneeruk
    Nakprasit, Kittikorn
    GRAPHS AND COMBINATORICS, 2018, 34 (02) : 349 - 354
  • [46] COMPLETE MINORS AND INDEPENDENCE NUMBER
    Fox, Jacob
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) : 1313 - 1321
  • [47] The lower bound on independence number
    李雨生
    CecilC.ROUSSEAU
    臧文安
    Science China Mathematics, 2002, (01) : 64 - 69
  • [48] Independence number in path graphs
    Knor, M
    Niepel, L
    COMPUTING AND INFORMATICS, 2004, 23 (02) : 179 - 187
  • [49] Maximum Modified Sombor Index of Unicyclic Graphs with Given Girth
    Nagarajan, Sethumadhavan
    Vijaya, A.
    IRANIAN JOURNAL OF MATHEMATICAL CHEMISTRY, 2024, 15 (02): : 117 - 122
  • [50] On the strength and independence number of graphs
    Ichishima, Rikio
    Muntaner-Batle, Francesc A.
    Takahashi, Yukio
    CONTRIBUTIONS TO MATHEMATICS, 2022, 6 : 25 - 29
12345