Mathematics – Combinatorics
Scientific paper
2012-03-18
Mathematics
Combinatorics
arXiv admin note: text overlap with arXiv:1109.4122
Scientific paper
Bedrossian characterized pairs of forbidden subgraphs which imply a 2-connected graph is Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions by restricting Fan-type and Ore-type degree conditions on the induced subgraphs. In particular, for a graph $G$ on $n$ vertices, an induced subgraph $R$ of $G$ is called $f$-heavy if for every two vertices $u,v\in V(R)$, $dist_{R}(u,v)=2$ implies that $max\{d(u),d(v)\}\geq n/2$. We say that $G$ is $R$-$f$-heavy if every induced subgraph of $G$ isomorphic to $R$ is $f$-heavy. We define $G$ to be claw-$o$-heavy if there are two end vertices of each induced subgraph of $G$ isomorphic to $K_{1,3}$ with degree sum at least $n$. In this paper we characterize all the connected graphs $R$ other than $P_3$ which imply that every 2-connected claw-$o$-heavy and $R$-$f$-heavy graph is Hamiltonian. Our result extends several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity.
No associations
LandOfFree
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 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 Heavy subgraphs for Hamiltonicity of 2-connected graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-617089