Premium
Hamiltonian graphs involving neighborhood unions
Author(s) -
Chen Guantao,
Shreve Warren E.,
Wei Bing
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20168
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , upper and lower bounds , hamiltonian (control theory) , bound graph , quartic graph , connectivity , discrete mathematics , hamiltonian path , graph power , line graph , mathematical analysis , mathematical optimization
Dirac proved that a graph G is hamiltonian if the minimum degree $\delta(G) \geq n/2$ , where n is the order of G . Let G be a graph and $A \subseteq V(G)$ . The neighborhood of A is $N(A)=\{ b: ab \in E(G)$ for some $a \in A\}$ . For any positive integer k , we show that every (2 k − 1)‐connected graph of order n ≥ 16 k 3 is hamiltonian if | N ( A )| ≥ n /2 for every independent vertex set A of k vertices. The result contains a few known results as special cases. The case of k = 1 is the classic result of Dirac when n is large and the case of k = 2 is a result of Broersma, Van den Heuvel, and Veldman when n is large. For general k , this result improves a result of Chen and Liu. The lower bound 2 k − 1 on connectivity is best possible in general while the lower bound 16 k 3 for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006