Domination Number and Hamiltonicity of Graphs

Rao Li 1
1Dept. of Mathematical Sciences University of South Carolina Aiken, Aiken, SC 29801

Abstract

Let \( G \) be a \( k \)-connected (\( k \geq 2 \)) graph of order \( n \). If \( \gamma(G^c) \geq n – k \), then \( G \) is Hamiltonian or \( K_k \vee K_{k+1}^c \), where \( \gamma(G^c) \) is the domination number of the complement of the graph \( G \).

Keywords: Hamiltonicity, domination number.