Toughness and Triangle-Free Graphs

Douglas Bauer, J. Van den Heuvel

Research output: Contribution to journalArticle

10 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)208-221
Number of pages14
JournalJournal of Combinatorial Theory, Series B
Volume65
Issue number2
DOIs
StatePublished - Jan 1 1995

Fingerprint

Triangle-free Graph
Toughness

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Cite this

Bauer, Douglas ; Van den Heuvel, J. / Toughness and Triangle-Free Graphs. In: Journal of Combinatorial Theory, Series B. 1995 ; Vol. 65, No. 2. pp. 208-221.
@article{0a4a662450234f5a851bf5d3bb79f38c,
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 = "Douglas Bauer and {Van den Heuvel}, J.",
year = "1995",
month = "1",
day = "1",
doi = "https://doi.org/10.1006/jctb.1995.1051",
language = "English (US)",
volume = "65",
pages = "208--221",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press Inc.",
number = "2",

}

Toughness and Triangle-Free Graphs. / Bauer, Douglas; Van den Heuvel, J.

In: Journal of Combinatorial Theory, Series B, Vol. 65, No. 2, 01.01.1995, p. 208-221.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Toughness and Triangle-Free Graphs

AU - Bauer, Douglas

AU - Van den Heuvel, J.

PY - 1995/1/1

Y1 - 1995/1/1

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.

UR - http://www.scopus.com/inward/record.url?scp=0041978476&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041978476&partnerID=8YFLogxK

U2 - https://doi.org/10.1006/jctb.1995.1051

DO - https://doi.org/10.1006/jctb.1995.1051

M3 - Article

VL - 65

SP - 208

EP - 221

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 2

ER -