1-tough cocomparability graphs are hamiltonian

Jitender S. Deogun; Dieter Kratsch; George Steiner

doi:10.1016/0012-365X(95)00359-5

1-tough cocomparability graphs are hamiltonian

Jitender S. Deogun, Dieter Kratsch, George Steiner

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chvàtal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.

Original language	English (US)
Pages (from-to)	99-106
Number of pages	8
Journal	Discrete Mathematics
Volume	170
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(95)00359-5
State	Published - Jun 10 1997
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(95)00359-5

Cite this

@article{aa15e9032599442983a6b1cd462c6c87,

title = "1-tough cocomparability graphs are hamiltonian",

abstract = "We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chv{\`a}tal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.",

author = "Deogun, {Jitender S.} and Dieter Kratsch and George Steiner",

note = "Funding Information: * Corresponding author. E-mail: steiner@mcmail.cis.mcmaster.ca. I This research was supported in part by the Office of Naval Research under Grant No. N0014-91-J-1693 and by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0001798.",

year = "1997",

month = jun,

day = "10",

doi = "10.1016/0012-365X(95)00359-5",

language = "English (US)",

volume = "170",

pages = "99--106",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - 1-tough cocomparability graphs are hamiltonian

AU - Deogun, Jitender S.

AU - Kratsch, Dieter

AU - Steiner, George

N1 - Funding Information: * Corresponding author. E-mail: steiner@mcmail.cis.mcmaster.ca. I This research was supported in part by the Office of Naval Research under Grant No. N0014-91-J-1693 and by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0001798.

PY - 1997/6/10

Y1 - 1997/6/10

N2 - We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chvàtal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.

AB - We show that every 1-tough cocomparability graph has a Hamilton cycle. This settles a conjecture of Chvàtal for the case of cocomparability graphs. Our approach is based on exploiting the close relationship of the problem to the scattering number and the path cover number.

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

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

U2 - 10.1016/0012-365X(95)00359-5

DO - 10.1016/0012-365X(95)00359-5

M3 - Article

AN - SCOPUS:0038282323

SN - 0012-365X

VL - 170

SP - 99

EP - 106

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

1-tough cocomparability graphs are hamiltonian

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this