Forbidden subgraphs for hamiltonicity of 1-tough graphs

Haitze J. Broersma, Binlong Li, Shenggui Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)
    15 Downloads (Pure)

    Abstract

    A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G − S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K_1 ∪ P_4 as the only open case.
    Original languageUndefined
    Pages (from-to)915-929
    Number of pages15
    JournalDiscussiones mathematicae. Graph theory
    Volume36
    Issue number4
    DOIs
    Publication statusPublished - Oct 2016

    Keywords

    • MSC-05C07
    • Hamiltonian graph
    • MSC-05C45
    • MSC-05C38
    • H-free graph
    • Forbidden subgraph
    • IR-101997
    • 1-tough
    • METIS-319456
    • EWI-27290
    • Toughness

    Cite this