Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs

Details Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs

2011-09-19

arxiv.org/abs/1109.4122v1

Mathematics

Combinatorics

Scientific paper

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 $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$-heavy if $G$ is $H$-heavy for every $H\in\mathcal{H}$. 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.

Affiliated with

Also associated with

No associations

Rating

Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97552