摘要
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 H of graphs, G is called H-heavy if G is H-heavy for every H ∈ 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.
源语言 | 英语 |
---|---|
页(从-至) | 1088-1103 |
页数 | 16 |
期刊 | SIAM Journal on Discrete Mathematics |
卷 | 26 |
期 | 3 |
DOI | |
出版状态 | 已出版 - 2012 |