Pairs of Heavy Subgraphs for Hamiltonicity of 2-Connected Graphs

DOI10.1137/11084786XMaRDI QIDQ4899047zbMATH OpenFDO

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

Publication date 4 January 2013

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

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

zbMATH Keywords

Hamilton cycleforbidden subgraphheavy subgraph

Mathematics Subject Classification ID

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

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.

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

Cited in

(18)

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