Hamiltonian Graphs with Large Neighborhood Unions

Guantao Chen1, Yiping Liu2
1 Department of Mathematics North Dakota State University Fargo, ND 58105
2Department of Mathematics Nanjin Normal University Nanjin, China

Abstract

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.