One of the fundamental results concerning cycles in graphs is due to Ore:
If \(G\) is a graph of order \(n \geq 3\) such that \(d(x) + d(y) \geq n\) for every pair of nonadjacent vertices \(x, y \in V(G)\), then \(G\) is hamiltonian.
We generalize this result using neighborhood unions of \(k\) independent vertices for any fixed integer \(k \geq 1\). That is, for \(A \subseteq V(G)\), let \(N(A) = \cup_{a \in A} N(a),\)
where \(N(a) = \{b : ab \in E(G)\}\) is the neighborhood of \(a\). In particular, we show:
In a \(4(k-1)\)-connected graph \(G\) of order \(n \geq 3\), if \(|N(S)|+|N(T)| \geq n\) for every two disjoint independent vertex sets \(S\) and \(T\) of \(k\) vertices, then \(G\) is hamiltonian.
A similar result for hamiltonian connected graphs is obtained too.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.