Abstract
Earlier results originating from Bedrossian’s PhD Thesis focus on characterizing pairs of forbidden subgraphs that imply hamiltonian properties. Instead of forbidding certain induced subgraphs, here we relax the requirements by imposing Ore-type degree conditions on the induced subgraphs. In particular, adopting the terminology introduced by Čada, for a graph G on n vertices and a fixed graph H, we say that G is H-o1-heavy if every induced subgraph of G isomorphic to H contains two nonadjacent vertices with degree sum at least n+1 in G. For a family F of graphs, G is called F-o1-heavy if G is H-o1-heavy for every H ∈ F. In this paper we characterize all connected graphs R and S other than P3 (the path on three vertices) such that every 2-connected {R,S}-o1-heavy graph is either a cycle or pancyclic, thereby extending previous results on forbidden subgraph conditions for pancyclicity and on heavy subgraph conditions for hamiltonicity.
Original language | English |
---|---|
Pages (from-to) | 649-667 |
Number of pages | 19 |
Journal | Graphs and combinatorics |
Volume | 31 |
Issue number | 3 |
DOIs | |
Publication status | Published - May 2015 |
Keywords
- MSC-05C
- Pancyclic graph
- Forbidden subgraph
- Hamiltonian graph
- o1-Heavy subgraph
- 2024 OA procedure