Hamiltonicity of Domination Critical Claw-Free Graphs

Abstract

A graph $G$ is said to be $k$-$\gamma$-edge critical if the domination number $\gamma (G)=k$ and $\gamma (G+uv)<k$ for every $uv\notin E(G)$. For the connected domination number ${\gamma }_c(G)=k$, the total domination number ${\gamma }_t(G)=k$ and the independent domination number $i(G)=k$, a $k$-${\gamma }_c$-edge critical graph, a $k$-${\gamma }_t$-edge critical graph and a $k$-$i$-edge critical graph are similarly defined. In our previous work, we proved that every $2$-connected $k$-${\gamma }_c$-edge critical graph is hamiltonian for $1\le k\le 3$ and we provided a class of $l$-connected $k$-${\gamma }_c$-edge critical non-hamiltonian graphs for $k\ge 4$ and $2\le l\le \frac{n-3}{k-1}$. The problem of interest is to determine a sufficient condition for $k$-${\gamma }_c$-edge critical graphs to be hamiltonian for $k\ge 4$. In this paper, we prove that every $2$-connected $4$-${\gamma }_c$-edge critical claw-free graph is hamiltonian. For $k\ge 5$, we provide a class of $k$-${\gamma }_c$-edge critical claw-free non-hamiltonian graphs of connectivity two. We further show that all $3$-connected $k$-${\gamma }_c$-edge critical claw-free graphs are hamiltonian for $1\le k\le 6$. Our methodology also establishes some results on the hamiltonian properties of $3$-connected $k$-$\mathcal{D}$-edge critical claw-free graphs where $\mathcal{D}\in \{\gamma ,{\gamma }_t,i\}$.