Neighborhood unions and a generalization of Dirac's theorem
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.
- A new sufficient condition for hamiltonian graphs
- A remark on Hamiltonian cycles
- Extremal problems involving neighborhood unions
- scientific article; zbMATH DE number 4053664 (Why is no real title available?)
- scientific article; zbMATH DE number 4089545 (Why is no real title available?)
- scientific article; zbMATH DE number 21736 (Why is no real title available?)
- scientific article; zbMATH DE number 867642 (Why is no real title available?)
- Neighbourhood unions and Hamiltonian properties in graphs
- New sufficient conditions for cycles in graphs
- Note on Hamilton Circuits
- Some Theorems on Abstract Graphs
- The effects of distance and neighborhood union conditions on hamiltonian properties in graphs
- Hamiltonian properties of graphs with large neighborhood unions
- On independent generalized degrees and independence numbers in \(K(1,m)\)- free graphs
- A generalization of Ore's Theorem involving neighborhood unions
- Extremal problems and generalized degrees
- A proof of a conjecture about \(D_ \lambda\)-paths in graphs with large neighborhood unions
- A generalization of Dirac's theorem for \(K(1,3)\)-free graphs
- Some elementary consequences of Perelman's canonical neighborhood theorem
- The neighborhood union of independent sets and hamiltonicity of graphs
- -neighborhoods and comparison theorems
- The effects of distance and neighborhood union conditions on hamiltonian properties in graphs
- scientific article; zbMATH DE number 15489 (Why is no real title available?)
- scientific article; zbMATH DE number 19187 (Why is no real title available?)
- Neighborhood unions and hamilton cycles
- 2‐neighborhoods and hamiltonian conditions
- A new neighborhood union condition for Hamiltonian graphs
- scientific article; zbMATH DE number 1501177 (Why is no real title available?)
- scientific article; zbMATH DE number 913288 (Why is no real title available?)
This page was built for publication: Neighborhood unions and a generalization of Dirac's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199474)
