Neighborhood unions and a generalization of Dirac's theorem (Q1199474): Difference between revisions

In the last few years, Ore's well-known sufficient condition for Hamiltonicity has been extended to so-called `neighborhood union conditions': If, for fixed integer \(k\geq 2\), the union of the neighborhoods of any \(k\) independent vertices is large enough (depending on \(k)\), then the graph is Hamiltonian. In contrast to these approaches, neighborhood unions of arbitrary (not necessarily independent) sets of \(k\) vertices are considered in this paper. A graph \(G\) is said to satisfy property \(\text{NC}_ k(G)\geq s\) if for each set \(S\) of \(k\) vertices of \(G\) we have \(\left|\bigcup_{x\in X}N(x)\right|\geq s\), where \(N(x)\) is the set of vertices adjacent to \(x\). The main theorem of the paper is: Let \(k\geq 2\) be an integer not greater than the minimum degree of a graph \(G\) with \(n\) vertices. Then \(\text{NC}_ k(G)\geq{n\over 2}+8k^ 3\) implies that \(G\) is Hamiltonian. The \(8k^ 3\)-part of the bound is not best possible. However, for \(k=2\) the following sharp result is given: Every sufficiently large 2-connected graph \(G\) with \(\text{NC}_ 2(G)\geq{n\over 2}\) is Hamiltonian. In the case \(k=2\), similar sufficient conditions in terms of \(\text{NC}_ 2(G)\) for the existence of paths, cycles, and matchings are given.