کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647658 | 1342365 | 2013 | 11 صفحه PDF | دانلود رایگان |
Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on these induced subgraphs. Let GG be a graph on nn vertices and HH be an induced subgraph of GG. HH is called oo-heavy if there are two nonadjacent vertices in HH with degree sum at least nn, and is called ff-heavy if for every two vertices u,v∈V(H)u,v∈V(H), dH(u,v)=2dH(u,v)=2 implies that max{d(u),d(v)}≥n/2max{d(u),d(v)}≥n/2. We say that GG is HH-oo-heavy (HH-ff-heavy) if every induced subgraph of GG isomorphic to HH is oo-heavy (ff-heavy). In this paper we characterize all connected graphs RR and SS other than P3P3 such that every 2-connected RR-ff-heavy and SS-ff-heavy (RR-oo-heavy and SS-ff-heavy, RR-ff-heavy and SS-free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs.
Journal: Discrete Mathematics - Volume 313, Issue 17, 6 September 2013, Pages 1715–1725