Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

DOI10.1142/S1793830914500438zbMATH Open1298.05191arXiv1212.6466OpenAlexW2080784768MaRDI QIDQ2920892FDOQ2920892

Authors: Bo Ning, Shenggui Zhang, Bing Chen 

Publication date: 29 September 2014

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Abstract: Let claw be the graph $K_{1,3}$. A graph $G$ on $ngeq3$ vertices is called emph{o}-heavy if each induced claw of $G$ has a pair of end-vertices with degree sum at least $n$, and 1-heavy if at least one end-vertex of each induced claw of $G$ has degree at least $n/2$. In this note, we show that every 2-connected $o$-heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman & Hedetniemi, Gould & Jacobson, and Shi on the existence of Hamilton cycles in graphs.

Full work available at URL: https://arxiv.org/abs/1212.6466

Recommendations

• Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs
• Hamilton cycles in claw-heavy graphs with Fan-type condition restricted to two induced subgraphs.
• Hamilton cycles in claw-heavy graphs
• Dirac's minimum degree condition restricted to claws
• On implicit heavy subgraphs and Hamiltonicity of 2-connected graphs

zbMATH Keywords

induced subgraphHamilton cycleclaw-free (1-heavy, 2-heavy, \(o\)-heavy) graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Graph theory with applications
• New sufficient conditions for cycles in graphs
• Forbidden subgraphs and Hamiltonian properties and graphs
• Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs
• Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs
• Degree conditions on induced claws
• Hamilton cycles in claw-heavy graphs
• Sufficient conditions for a graph to be Hamiltonian

Cited In (2)

• Hamilton cycles in almost distance-hereditary graphs
• Hamilton cycles in claw-heavy graphs

This page was built for publication: Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920892)