Hamiltonian Properties of Independent Domination Critical Graphs

摘要

A graph G is k-edge-i-critical if it has independent domination number i(G) = k, and i(G + xy) < i(G) whenever xy ￠ E(G). The following results are obtained for 3-edge-i-critical graphs G: (a) If δ ≥ 3, then G is hamiltonian (b) If δ = 2, then there is exactly one family of non-hamiltonian graphs; and (c) If∣V(G)∣ > 6, then G has a Hamilton path. The proofs of these results rely on a closure operation, a characterisation of the 2-connected, 3-edge-i-critical graphs with δ = 2, and a characterisation of the 3-edge-i-critical graphs with a cut vertex.