Neighborhood unions and a generalization of Dirac's theorem
type: Item
instance of: scholarly article
title: Neighborhood unions and a generalization of Dirac's theorem
zbMATH Open document ID: 0778.05055
DOI: 10.1016/0012-365X(92)90132-Y
author: Ralph Faudree
author: Ronald Gould
author: Michael Jacobson
author: Linda Lesniak
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 94347
zbMATH Keywords: Hamiltonian graphs
zbMATH Keywords: Ore's condition
zbMATH Keywords: neighborhood union conditions
zbMATH Keywords: Hamiltonicity
zbMATH Keywords: paths
zbMATH Keywords: cycles
zbMATH Keywords: matchings
reviewed by: Erich Prisner
MaRDI profile type: Publication
cites work: Q3818315
cites work: Some Theorems on Abstract Graphs
cites work: New sufficient conditions for cycles in graphs
cites work: Q3981351
cites work: Extremal problems involving neighborhood unions
cites work: Neighbourhood unions and Hamiltonian properties in graphs
cites work: Q3789605
cites work: A new sufficient condition for hamiltonian graphs
cites work: A remark on Hamiltonian cycles
cites work: Q4873754
cites work: The effects of distance and neighborhood union conditions on hamiltonian properties in graphs
cites work: Note on Hamilton Circuits
description: scientific article; zbMATH DE number 94347