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

    Chen, Xiaodong ; Li, MingChu ; Liao, Wei ; Broersma, Haitze J. / Hamiltonian properties of almost locally connected claw-free graphs. In: Ars combinatoria. 2016 ; Vol. 124. pp. 95-109.
    @article{14f0afc5ed0943a0a247e5efa94d3b81,
    title = "Hamiltonian properties of almost locally connected claw-free graphs",
    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].",
    keywords = "EWI-27151, MSC-05C, IR-101070, METIS-318496, Hamilton-connected, Hamiltonian, almost locally connected, Claw-free graph",
    author = "Xiaodong Chen and MingChu Li and Wei Liao and Broersma, {Haitze J.}",
    note = "eemcs-eprint-27151",
    year = "2016",
    month = "1",
    language = "Undefined",
    volume = "124",
    pages = "95--109",
    journal = "Ars combinatoria",
    issn = "0381-7032",
    publisher = "Charles Babbage Research Centre",

    }

    Hamiltonian properties of almost locally connected claw-free graphs. / Chen, Xiaodong; Li, MingChu; Liao, Wei; Broersma, Haitze J.

    In: Ars combinatoria, Vol. 124, 01.2016, p. 95-109.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Hamiltonian properties of almost locally connected claw-free graphs

    AU - Chen, Xiaodong

    AU - Li, MingChu

    AU - Liao, Wei

    AU - Broersma, Haitze J.

    N1 - eemcs-eprint-27151

    PY - 2016/1

    Y1 - 2016/1

    N2 - 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].

    AB - 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].

    KW - EWI-27151

    KW - MSC-05C

    KW - IR-101070

    KW - METIS-318496

    KW - Hamilton-connected

    KW - Hamiltonian

    KW - almost locally connected

    KW - Claw-free graph

    M3 - Article

    VL - 124

    SP - 95

    EP - 109

    JO - Ars combinatoria

    JF - Ars combinatoria

    SN - 0381-7032

    ER -