Hamiltonian properties of graphs with large neighborhood unions (Q1182981): Difference between revisions

Various degree and neighborhood conditions are shown to imply long cycles in a graph, and some of these new conditions are shown to generalize well-known conditions for Hamiltonicity of a graph. It was proved by the first and third author, \textit{A. Morgana} and \textit{E. F. Schmeichel} [Discrete Math. 79, No. 1, 59-70 (1990; Zbl 0713.05041)] that if \(G\) is a 1-tough graph with \(\sigma_ 3(G)\geq n\geq 3\) \((\sigma_ k(G)\) is the minimum sum of degrees of a set of \(k\) independent vertices of \(G\)), then \(G\) contains a cycle of length at least \(\min\{n,n+{1\over 3}\sigma_ 3(G)-\alpha(G)\}\). It is shown that a corollary of this result is that any 2-connected graph \(G\) of order \(n\) with \(NC(G)\geq (2n-3)/3\) is Hamiltonian, where \(NC(G)\) is the minimum number of vertices in the union of the neighborhoods of any pair of nonadjacent vertices. This improves the result of \textit{R. J. Faudree, R. J. Gould, M. S. Jacobson} and \textit{R. H. Schelp} [J. Combin. Theory, Ser. B 47, No. 1, 1-9 (1989; Zbl 0677.05056)] on neighborhood unions. The result of the first author et. al. that a graph \(G\) of order \(n\) with \(\sigma(G)\geq n+2\) has a cycle of length at least \(\min\{n,n+{1\over 3}\sigma_ 3(G)-\alpha(G)\}\) is shown to imply the classical result of Dirac (minimum degree \(n/2\) implies a Hamiltonian cycle) and the previous result on neighborhood unions. The authors prove that if \(G\) is a 2-connected graph with \(\sigma_ 3(G)\geq n+2\), then \(G\) contains a cycle of length \(\min\{n,2NC2(G)\}\), where \(NC2(G)\) is the minimum number of vertices in the union of the neighborhoods of any pair of vertices at distance 2 in the graph. Conditions of a similar nature are shown to imply the existence of a cycle \(C\) in a graph \(G\) such that \(G-V(C)\) has only small components.