Semi-independence number of a graph and the existence of Hamiltonian circuits (Q1088684): Difference between revisions

Given vertices a and b of a graph G, let T be the collection of vertices that are not adjacent to either a or b. Denote by \(\alpha_{ab}\) the number of elements in \(T\cup \{a,b\}\) and by \(\delta_{ab}\) the minimum degree in G of a vertex in T. For a 2-connected graph G with \(\alpha_{ab}\leq \delta_{ab}\), it is shown that G is Hamiltonian if and only if \(G+ab\) is Hamiltonian. Slightly stronger results with more complicated conditions are proved, and several well-known results on Hamiltonian cycles are shown to be corollaries. A dual closure property using the parameters \(\alpha_{ab}\) and \(\delta_{ab}\), and patterned after the closure property of \textit{J. A. Bondy} and \textit{V. Chvátal} [Discrete Math. 15, 111-135 (1976; Zbl 0331.05138)] is also introduced.