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

DOI10.1142/S1793830914500438MaRDI QIDQ2920892zbMATHOpenAlexFDO

Authors Bo Ning, Shenggui Zhang, Bing Chen

Publication date 29 September 2014

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

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

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)

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.

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

Cites work

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

Cited in

(8)

• Hamilton cycles in claw-heavy graphs with Fan-type condition restricted to two induced subgraphs.
• Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs
• Hamilton cycles in claw-heavy graphs
• Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity
• Hamilton cycles in almost distance-hereditary graphs
• Solution to a problem on Hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
• Hamiltonian claw-free graphs and \(o\)-heavy graphs involving induced cycles
• Dominating set and Hamiltonicity 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)