Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs

科研成果: 期刊稿件文章同行评审

14 引用 (Scopus)

摘要

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

指纹

探究 'Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此