Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs

DOI10.1137/11084786XzbMATH Open1256.05052arXiv1109.4122MaRDI QIDQ4899047FDOQ4899047

Ying Wang, Shenggui Zhang, Binlong Li, Zdeněk Ryjáček

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $G$ be a graph on $n$ vertices. An induced subgraph $H$ of $G$ is called heavy if there exist two nonadjacent vertices in $H$ with degree sum at least $n$ in $G$. We say that $G$ is $H$-heavy if every induced subgraph of $G$ isomorphic to $H$ is heavy. For a family $mathcalH$ of graphs, $G$ is called $mathcalH$-heavy if $G$ is $H$-heavy for every $HinmathcalH$. In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (the path on three vertices) such that every 2-connected $R,S$-heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian graphs.

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

Recommendations

• On implicit heavy subgraphs and Hamiltonicity of 2-connected graphs
• Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs
• Heavy subgraphs, stability and Hamiltonicity
• Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs
• scientific article; zbMATH DE number 1161312
• A triple of heavy subgraphs ensuring pancyclicity of 2-connected graphs
• Clique-heavy subgraphs and pancyclicity of 2-connected graphs
• Two forbidden subgraph pairs for Hamiltonicity of 3-connected graphs
• Hamilton cycles in implicit 2-heavy graphs
• A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs

zbMATH Keywords

Hamilton cycleforbidden subgraphheavy subgraph

Mathematics Subject Classification ID

Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cited In (18)

• Degree and neighborhood intersection conditions restricted to induced subgraphs ensuring Hamiltonicity of graphs
• Heavy subgraphs, stability and Hamiltonicity
• Heavy subgraph pairs for traceability of block-chains
• Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity
• Extremal problems of Erdős, Faudree, Schelp and Simonovits on paths and cycles
• Solution to a problem on Hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
• Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs
• Conditions for graphs to be path partition optimal
• Degree conditions restricted to induced paths for Hamiltonicity of claw-heavy graphs
• Hamilton cycles in almost distance-hereditary graphs
• Clique-heavy subgraphs and pancyclicity of 2-connected graphs
• Extremal problems on the Hamiltonicity of claw-free graphs
• A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs
• Forbidden subgraphs for longest cycles to contain vertices with large degrees
• Implicit degree condition for Hamiltonicity of 2-heavy graphs
• On implicit heavy subgraphs and Hamiltonicity of 2-connected graphs
• Characterizing heavy subgraph pairs for pancyclicity
• On traceability of claw-\({o_{-1}}\)-heavy graphs

This page was built for publication: Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs

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