Forbidden subgraphs for hamiltonicity of 1-tough graphs

Binlong Li, Hajo J. Broersma, Shenggui Zhang

    Research output: Contribution to journalArticleAcademicpeer-review

    8 Citations (Scopus)
    24 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 languageEnglish
    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
    • 1-tough
    • Toughness
    • 2023 OA procedure

    Fingerprint

    Dive into the research topics of 'Forbidden subgraphs for hamiltonicity of 1-tough graphs'. Together they form a unique fingerprint.

    Cite this