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 条
[1]  
Barefoot C., 1987, J Comb Math Comb Comput, V1, P12
[2]   RECOGNIZING TOUGH GRAPHS IS NP-HARD [J].
BAUER, D ;
HAKIMI, SL ;
SCHMEICHEL, E .
DISCRETE APPLIED MATHEMATICS, 1990, 28 (03) :191-195
[3]  
Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6
[4]   AN UPPER BOUND ON THE SHORTNESS EXPONENT OF 1-TOUGH, MAXIMAL PLANAR GRAPHS [J].
DILLENCOURT, MB .
DISCRETE MATHEMATICS, 1991, 90 (01) :93-97
[5]   TOUGHNESS AND DELAUNAY TRIANGULATIONS [J].
DILLENCOURT, MB .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) :575-601
[6]  
Goddard W., 1990, Quaest. Math., V13, P217
[7]   TOUGHNESS AND NONHAMILTONICITY OF POLYHEDRAL GRAPHS [J].
HARANT, J .
DISCRETE MATHEMATICS, 1993, 113 (1-3) :249-253
[8]   HAMILTONIAN RESULTS IN K1,3 FREE GRAPHS [J].
MATTHEWS, MM ;
SUMNER, DP .
JOURNAL OF GRAPH THEORY, 1984, 8 (01) :139-146
[9]   UNIQUENESS AND FAITHFULNESS OF EMBEDDING OF TOROIDAL GRAPHS [J].
NEGAMI, S .
DISCRETE MATHEMATICS, 1983, 44 (02) :161-180
[10]  
Pippert R.E., 1972, Lecture Notes in Math, V303, P225