Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs

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+$k - \gamma _{ \times 2}^ + $-stable if γ×2 (G + uv) = k for any uv ∉ E(G) and is said to be k-γ×2-$k - \gamma _{ \times 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+$k - \gamma _{ \times 2}^ + $-stable graphs and k-γ×2-$k - \gamma _{ \times 2}^ - $-stable graphs.

Keywords

• double domination
• critical
• stable
• hamiltonian
• 05c69
• 05c45