Toughness and vertex degrees

D. Bauer, Haitze J. Broersma, J. van den Heuvel, N. Kahl, E. Schmeichel

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

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 is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.
Original languageUndefined
Pages (from-to)209-219
Number of pages11
JournalJournal of graph theory
Volume72
Issue number2
DOIs
Publication statusPublished - 2013

Keywords

  • MSC-05C
  • Toughness
  • EWI-23370
  • IR-86131
  • Degree condition
  • METIS-297654
  • Best monotone theorem

Cite this

Bauer, D., Broersma, H. J., van den Heuvel, J., Kahl, N., & Schmeichel, E. (2013). Toughness and vertex degrees. Journal of graph theory, 72(2), 209-219. https://doi.org/10.1002/jgt.21639
Bauer, D. ; Broersma, Haitze J. ; van den Heuvel, J. ; Kahl, N. ; Schmeichel, E. / Toughness and vertex degrees. In: Journal of graph theory. 2013 ; Vol. 72, No. 2. pp. 209-219.
@article{6ea5f99eab6643c094ede62111c4069f,
title = "Toughness and vertex degrees",
abstract = "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 is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.",
keywords = "MSC-05C, Toughness, EWI-23370, IR-86131, Degree condition, METIS-297654, Best monotone theorem",
author = "D. Bauer and Broersma, {Haitze J.} and {van den Heuvel}, J. and N. Kahl and E. Schmeichel",
note = "eemcs-eprint-23370",
year = "2013",
doi = "10.1002/jgt.21639",
language = "Undefined",
volume = "72",
pages = "209--219",
journal = "Journal of graph theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "2",

}

Bauer, D, Broersma, HJ, van den Heuvel, J, Kahl, N & Schmeichel, E 2013, 'Toughness and vertex degrees' Journal of graph theory, vol. 72, no. 2, pp. 209-219. https://doi.org/10.1002/jgt.21639

Toughness and vertex degrees. / Bauer, D.; Broersma, Haitze J.; van den Heuvel, J.; Kahl, N.; Schmeichel, E.

In: Journal of graph theory, Vol. 72, No. 2, 2013, p. 209-219.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Toughness and vertex degrees

AU - Bauer, D.

AU - Broersma, Haitze J.

AU - van den Heuvel, J.

AU - Kahl, N.

AU - Schmeichel, E.

N1 - eemcs-eprint-23370

PY - 2013

Y1 - 2013

N2 - 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 is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.

AB - 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 is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.

KW - MSC-05C

KW - Toughness

KW - EWI-23370

KW - IR-86131

KW - Degree condition

KW - METIS-297654

KW - Best monotone theorem

U2 - 10.1002/jgt.21639

DO - 10.1002/jgt.21639

M3 - Article

VL - 72

SP - 209

EP - 219

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 2

ER -

Bauer D, Broersma HJ, van den Heuvel J, Kahl N, Schmeichel E. Toughness and vertex degrees. Journal of graph theory. 2013;72(2):209-219. https://doi.org/10.1002/jgt.21639