More Progress on Tough Graphs - The Y2K Report

Doug Bauer; Hajo Broersma; Edward Schmeichel

doi:10.1016/S1571-0653(04)00055-1

More Progress on Tough Graphs - The Y2K Report

Doug Bauer
, Hajo Broersma
, Edward Schmeichel

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Conference article › Academic › peer-review

380 Downloads (Pure)

Abstract

We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/4−ϵ)-tough nontraceable graph. We continue our quadrennial survey of results that relate the toughness of a graph to its cycle structure.

Original language	English
Pages (from-to)	63-80
Journal	Electronic notes in discrete mathematics
Volume	11
DOIs	https://doi.org/10.1016/S1571-0653(04)00055-1
Publication status	Published - Jul 2002
Event	Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications - Kalamazoo , United States Duration: 4 Jun 2000 → 9 Jun 2000 Conference number: 9

Access to Document

10.1016/S1571-0653(04)00055-1

Bauer02moreAccepted author version, 744 KB

Cite this

@article{e2bb2e3e0f134ec88ba0e84fe4abb50e,

title = "More Progress on Tough Graphs - The Y2K Report",

abstract = "We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/4−ϵ)-tough nontraceable graph. We continue our quadrennial survey of results that relate the toughness of a graph to its cycle structure.",

author = "Doug Bauer and Hajo Broersma and Edward Schmeichel",

year = "2002",

month = jul,

doi = "10.1016/S1571-0653(04)00055-1",

language = "English",

volume = "11",

pages = "63--80",

journal = "Electronic notes in discrete mathematics",

issn = "1571-0653",

publisher = "Elsevier",

note = "Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications ; Conference date: 04-06-2000 Through 09-06-2000",

}

TY - JOUR

T1 - More Progress on Tough Graphs - The Y2K Report

AU - Bauer, Doug

AU - Broersma, Hajo

AU - Schmeichel, Edward

N1 - Conference code: 9

PY - 2002/7

Y1 - 2002/7

N2 - We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/4−ϵ)-tough nontraceable graph. We continue our quadrennial survey of results that relate the toughness of a graph to its cycle structure.

AB - We now know that not every 2-tough graph is hamiltonian. In fact for every ϵ > 0, there exists a (9/4−ϵ)-tough nontraceable graph. We continue our quadrennial survey of results that relate the toughness of a graph to its cycle structure.

U2 - 10.1016/S1571-0653(04)00055-1

DO - 10.1016/S1571-0653(04)00055-1

M3 - Conference article

SN - 1571-0653

VL - 11

SP - 63

EP - 80

JO - Electronic notes in discrete mathematics

JF - Electronic notes in discrete mathematics

T2 - Ninth Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms and Applications

Y2 - 4 June 2000 through 9 June 2000

ER -

More Progress on Tough Graphs - The Y2K Report

Abstract

Access to Document

Fingerprint

Cite this