Maximum and minimum toughness of graphs of small genus

被引:6
作者
Goddard, W
Plummer, MD
Swart, HC
机构
[1] UNIV NATAL,DURBAN,SOUTH AFRICA
[2] VANDERBILT UNIV,DEPT MATH,NASHVILLE,TN 37240
关键词
D O I
10.1016/S0012-365X(96)00238-5
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A new lower bound on the toughness t(G) of a graph G in terms of its connectivity rc(G) and genus gamma(G) is obtained. For gamma > 0, the bound is sharp via an infinite class of extremal graphs all of girth 4. For planar graphs, the bound is t(G)> kappa(G)/2 - 1. For kappa = 1 this bound is not sharp, but for each kappa = 3,4,5 and any epsilon > 0, infinite families of graphs {G(kappa,epsilon)} are provided with kappa(G(kappa,epsilon)) = kappa, but t(G(kappa,epsilon)) < kappa/2 - 1 + epsilon. Analogous investigations on the torus are carried out, and finally the question of upper bounds is discussed. Several unanswered questions are posed.
引用
收藏
页码:329 / 339
页数:11
相关论文
共 13 条
[11]  
Ringel G., 1965, ABH MATH SEM HAMBURG, V28, P139
[12]  
SCHMEICHEL EF, 1979, J COMB THEORY B, V27, P198, DOI 10.1016/0095-8956(79)90081-9
[13]  
[No title captured]