Hamiltonian Properties of Independent Domination Critical Graphs

Abstract

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 \notin E(G) \). The following results are obtained for \( 3 \)-edge-\( i \)-critical graphs \( G \):

1. If \( \delta \geq 3 \), then \( G \) is hamiltonian.
2. If \( \delta = 2 \), then there is exactly one family of non-hamiltonian graphs.
3. If \( |V(G)| > 6 \), then \( G \) has a Hamilton path.

The proofs of these results rely on a closure operation, a characterization of the \( 2 \)-connected, \( 3 \)-edge-\( i \)-critical graphs with \( \delta = 2 \), and a characterization of the \( 3 \)-edge-\( i \)-critical graphs with a cut vertex.