The neighborhood union of independent sets and hamiltonicity of graphs (Q2643317)

Two classic sufficient degree conditions for Hamiltonian graphs obtained by Dirac and Ore are: Theorem 1. (Dirac). Let \(G\) be a graph of order \(n\geq 3\). If \(\delta(G)\geq n/2\) then \(G\) is Hamiltonian. Theorem 2. (Ore) Let \(G\) be a graph of order \(n\geq 3\). If \(\deg(u)+ \deg(v)\geq n\) for every pair \(u\), \(v\) of nonadjacent vertices of \(G\) then \(G\) is Hamiltonian. A natural generalization of the above results is to replace the degree of each vertex by the degree of a set of vertices. Let \(G\) be a graph with vertex set \(V(G)\). For each vertex \(u\) in \(G\), let \(N(u)\) be the neighborhood of \(u\). For \(U\subseteq V(G)\), let \(N(U)=\bigcup N(u)\), where \(u\in U\). The authors prove the following theorem. Theorem 3. For any two positive integers \(s\) and \(t\), there exists a positive integer \(N(s, t)\) such that every \((s+t)\)-connected graph \(G\) of order \(n\geq N(s, t)\) is Hamiltonian if \(|N(S)|+ |N(T)|\geq n\) for every two disjoint independent sets \(S\), \(T\) with \(|S|= s\) and \(|T|= t\).