Toughness and Vertex Degrees

被引：9

作者：

Bauer, D. ^{[1
]}

Broersma, H. J. ^{[2
]}

van den Heuvel, J. ^{[3
]}

Kahl, N. ^{[4
]}

Schmeichel, E. ^{[5
]}

机构：

[1] Stevens Inst Technol, Dept Math Sci, Hoboken, NJ 07030 USA

[2] Univ Durham, Sch Engn & Comp Sci, Durham DH1 3LE, England

[3] London Sch Econ, Dept Math, London WC2A 2AE, England

[4] Seton Hall Univ, Dept Math & Comp Sci, S Orange, NJ 07079 USA

[5] San Jose State Univ, Dept Math, San Jose, CA 95192 USA

来源：

JOURNAL OF GRAPH THEORY | 2013年 / 72卷 / 02期

基金：

英国工程与自然科学研究理事会;

关键词：

degree sequences; toughness; best monotone theorem;

D O I：

10.1002/jgt.21639

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t-tough. We first give a best monotone theorem when t=1, but then show that for any integer k=1, a best monotone theorem for t=1k=1 requires at least f(k).|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k?8. When t<1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees. (C) 2012 Wiley Periodicals, Inc. J Graph Theory 72: 209-219, 2013

引用

页码：209 / 219

页数：11

共 7 条

[1] REALIZABILITY AND UNIQUENESS IN GRAPHS [J].

AIGNER, M ;

TRIESCH, E .

DISCRETE MATHEMATICS, 1994, 136 (1-3) :3-20

[2]

[Anonymous], 2001, Introduction to Graph Theory

[3]

[Anonymous], 1972, Journal of combinatorial theory, DOI DOI 10.1016/0095-8956(72)90020-2

[4]

Boesch F. T., 1974, Journal of Combinatorial Theory, Series B, V16, P162, DOI 10.1016/0095-8956(74)90058-6

[5]

Bondy J. A., 1969, STUD SCI MATH HUNG, V4, P473

[6]

Hardy GH, 1918, P LOND MATH SOC, V17, P75

[7]

Kriesell M., 2007, PREPRINT

← 1 →