Hamiltonicity in 3-domination-critical graphs with \(\alpha= \delta+2\)
Let \(\delta, \gamma\) and \(\alpha\) be respectively the minimum degree, the domination number and the independence number of a graph \(G\). The graph \(G\) is 3-\(\gamma\)-critical if \(\gamma = 3\) and the addition of any edge decreases \(\gamma\) by 1. It was conjectured that any connected 3-\(\gamma\)-critical graph with \(\delta \geq 2\) is Hamiltonian. In \textit{O. Faravon, F. Tian} and \textit{L. Zhang} [J. Graph Theory 25, No. 3, 173-184 (1997; Zbl 0881.05066)] it was proved that \(\alpha \leq \delta + 2\), and moreover, \(G\) is Hamiltonian if \(\alpha \leq \delta + 1\). In the present paper it is shown that \(G\) is Hamiltonian if \(\alpha = \delta + 2\), and thus the conjecture is proved. A class of 3-\(\gamma\)-critical graphs with \(\alpha = \delta + 2\) is provided as well.
scientific article; zbMATH DE number 1274839
scientific article