Toughness and Triangle-Free Graphs

D. Bauer; J. van den Heuvel; E. Schmeichel

doi:10.1006/jctb.1995.1051

Toughness and Triangle-Free Graphs

D. Bauer, J. van den Heuvel, E. Schmeichel

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic

12 Citations (Scopus)

96 Downloads (Pure)

Abstract

In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.

Original language	English
Pages (from-to)	208-221
Journal	Journal of Combinatorial Theory, Series B
Volume	65
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1995.1051
Publication status	Published - 1995

Access to Document

10.1006/jctb.1995.1051Licence: Other

Bauer95toughnessFinal published version, 520 KBLicence: Other

Cite this

@article{ee6816c502384edea90756aca379d388,

title = "Toughness and Triangle-Free Graphs",

abstract = "In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.",

author = "D. Bauer and {van den Heuvel}, J. and E. Schmeichel",

year = "1995",

doi = "10.1006/jctb.1995.1051",

language = "English",

volume = "65",

pages = "208--221",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press",

number = "2",

}

TY - JOUR

T1 - Toughness and Triangle-Free Graphs

AU - Bauer, D.

AU - van den Heuvel, J.

AU - Schmeichel, E.

PY - 1995

Y1 - 1995

N2 - In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.

AB - In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t.

U2 - 10.1006/jctb.1995.1051

DO - 10.1006/jctb.1995.1051

M3 - Article

SN - 0095-8956

VL - 65

SP - 208

EP - 221

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Toughness and Triangle-Free Graphs

Abstract

Access to Document

Fingerprint

Cite this