Maximum genus, independence number and girth

被引：0
作者：
Huang, YQ
Liu, YP
机构：
[1] Normal Univ Hunan, Dept Math, Changsha 410081, Peoples R China
[2] No Jiaotong Univ, Dept Math, Beijing 100044, Peoples R China
来源：
CHINESE ANNALS OF MATHEMATICS SERIES B | 2000年 / 21卷 / 01期
关键词：
maximum genus; Betti deficiency; independence number; girth;
D O I：
10.1142/S025295990000011X
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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.
引用
收藏
页码：77 / 82
页数：6
相关论文
共 14 条
[1]  
Bondy J.A., 2008, GRAD TEXTS MATH
[2]   A tight lower bound on the maximum genus of a simplicial graph [J].
Chen, J ;
Kanchi, SP ;
Gross, JL .
DISCRETE MATHEMATICS, 1996, 156 (1-3) :83-102
[3]   Maximum genus and connectivity [J].
Chen, JE ;
Archdeacon, D ;
Gross, JL .
DISCRETE MATHEMATICS, 1996, 149 (1-3) :19-29
[4]  
HUANG LF, 1996, AUSTRALASIAN J COMBI, V14, P187
[5]  
HUANG Y, 1998, SCI CHINA SER A, V28, P223
[6]  
HUANG Y, 1997, CHIN ANN MATH A, V18, P587
[7]   Maximum genus and maximum nonseparating independent set of a 3-regular graph [J].
Huang, YQ ;
Liu, YP .
DISCRETE MATHEMATICS, 1997, 176 (1-3) :149-158
[8]  
KANCHI SP, 1992, UNPUB TIGHT LOWER BO
[9]  
LIU Y, 1994, EMBEDDABILITY GRAPHS
[10]  
NEBESKY L, 1981, CZECH MATH J, V31, P604
12