摘要
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 G be a graph on n vertices and H be an induced subgraph of G. H is called o-heavy if there are two nonadjacent vertices in H with degree sum at least n, and is called f-heavy if for every two vertices u,v ∈ V(H), dH(u,v)=2 implies that max{d(u),d(v)}≥n/2. We say that G is H-o-heavy (H-f-heavy) if every induced subgraph of G isomorphic to H is o-heavy (f-heavy). In this paper we characterize all connected graphs R and S other than P3 such that every 2-connected R-f-heavy and S-f-heavy (R-o-heavy and S-f-heavy, R-f-heavy and S-free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs.
源语言 | 英语 |
---|---|
页(从-至) | 1715-1725 |
页数 | 11 |
期刊 | Discrete Mathematics |
卷 | 313 |
期 | 17 |
DOI | |
出版状态 | 已出版 - 2013 |