Authors: P. Kaemawichanurat Title: Hamiltonicities of double domination critical and stable claw-free graphs Source: Discussiones Mathematicae Graph Theory Received 30.10.2017, Revised 07.05.2018, Accepted 07.05.2018, doi: 10.7151/dmgt.2148 | |
Abstract: A graph G with the double domination number γ_{× 2}(G) = k is said to be k-γ_{× 2}-critical if γ_{× 2}(G + uv) < k for any uv ∉ E(G). On the other hand, a graph G with γ_{× 2}(G) = k is said to be k-γ^{+}_{× 2}-stable if γ_{× 2}(G + uv) = k for any uv ∉ E(G) and is said to be k-γ^{-}_{× 2}-stable if γ_{× 2}(G - uv) = k for any uv ∈E(G). The problem of interest is to determine whether or not 2-connected k-γ_{× 2}-critical graphs are Hamiltonian. In this paper, for k ≥ 4, we provide a 2-connected k-γ_{× 2}-critical graph which is non-Hamiltonian. We prove that all 2-connected k-γ_{× 2}-critical claw-free graphs are Hamiltonian when 2 ≤ k ≤ 5. We show that the condition claw-free when k = 4 is best possible. We further show that every 3-connected k-γ_{× 2}-critical claw-free graph is Hamiltonian when 2 ≤ k ≤ 7. We also investigate Hamiltonian properties of k-γ^{+}_{× 2}-stable graphs and k-γ^{-}_{× 2}-stable graphs. | |
Keywords: double domination, critical, stable, Hamiltonian | |
Links: |