Hamiltonian properties of almost locally connected claw-free graphs

Xiaodong Chen, MingChu Li, Wei Liao, Haitze J. Broersma

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Downloads (Pure)

    Abstract

    A vertex v of a graph G is locally connected if the set of neighbors N(v) of v induces a connected subgraph in G. Let B(G) denote the set of vertices of G that are not locally connected. Then G is almost locally connected if B(G) is an independent set and for any vertex x in B(G), there is a vertex y in V(G) - x such that N(x) ∪ y induces a connected subgraph of G. The main result of this paper is that an almost locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected. This generalizes the result by Asratian that a locally connected claw-free graph on at least 4 vertices is Hamilton-connected if and only if it is 3-connected [Journal of Graph Theory 23 (1996) 191–201].
    Original languageUndefined
    Pages (from-to)95-109
    Number of pages15
    JournalArs combinatoria
    Volume124
    Publication statusPublished - Jan 2016

    Keywords

    • EWI-27151
    • MSC-05C
    • IR-101070
    • METIS-318496
    • Hamilton-connected
    • Hamiltonian
    • almost locally connected
    • Claw-free graph

    Cite this