Hamiltonicity in 3-domination-critical graphs with α = δ + 2 Original Research Article

Let δ, γ, and α be respectively the minimum degree, the domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph with δ ⩾ 2 is hamiltonian. In Fararon et al. (J. Graph Theory, 25 (1997) 173–184.) it was proved α ⩽ δ + 2; and moreover, if α ⩽ δ + 1, then G is hamiltonian. Here we show that if α = δ + 2 then G is hamiltonian, and thus prove the conjecture. We also give a class of 3-γ-critical graphs with α = δ + 2.