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 条
  • [21] The hub number, girth and Mycielski graphs
    Liu, Xiaoping
    Dang, Zhilan
    Wu, Baoyindureng
    INFORMATION PROCESSING LETTERS, 2014, 114 (10) : 561 - 563
  • [22] On the number of linear hypergraphs of large girth
    Balogh, Jozsef
    Li, Lina
    JOURNAL OF GRAPH THEORY, 2020, 93 (01) : 113 - 141
  • [23] On the cop number of graphs of high girth
    Bradshaw, Peter
    Hosseini, Seyyed Aliasghar
    Mohar, Bojan
    Stacho, Ladislav
    JOURNAL OF GRAPH THEORY, 2023, 102 (01) : 15 - 34
  • [24] Graphs with maximum size and lower bounded girth
    Abajo, E.
    Dianez, A.
    APPLIED MATHEMATICS LETTERS, 2012, 25 (03) : 575 - 579
  • [25] Maximum Bisections of Graphs with Girth at Least Six
    Wu, Shufei
    Xiong, Xiaobei
    GRAPHS AND COMBINATORICS, 2024, 40 (06)
  • [26] On the Maximum Clique and the Maximum Independence Numbers of a Graph
    Maden, A. Dilek
    Buyukkose, Serife
    NUMERICAL ANALYSIS AND APPLIED MATHEMATICS ICNAAM 2011: INTERNATIONAL CONFERENCE ON NUMERICAL ANALYSIS AND APPLIED MATHEMATICS, VOLS A-C, 2011, 1389
  • [27] Sharp Upper Bounds on the k-Independence Number in Graphs with Given Minimum and Maximum Degree
    Suil, O.
    Shi, Yongtang
    Taoqiu, Zhenyu
    GRAPHS AND COMBINATORICS, 2021, 37 (02) : 393 - 408
  • [28] Sharp Upper Bounds on the k-Independence Number in Graphs with Given Minimum and Maximum Degree
    Suil O
    Yongtang Shi
    Zhenyu Taoqiu
    Graphs and Combinatorics, 2021, 37 : 393 - 408
  • [29] A note on generalized chromatic number and generalized girth
    Bollobás, B
    West, DB
    DISCRETE MATHEMATICS, 2000, 213 (1-3) : 29 - 34
  • [30] A generalization of the independence number
    Katona, Gyula O. H.
    DISCRETE APPLIED MATHEMATICS, 2022, 321 : 1 - 3
12345