### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 649-667 |

Number of pages | 19 |

Journal | Graphs and combinatorics |

Volume | 31 |

Issue number | 3 |

DOIs | |

State | Published - May 2015 |

### Fingerprint

### Keywords

- EWI-25946
- MSC-05C
- Pancyclic graph
- IR-95792
- Forbidden subgraph
- Hamiltonian graph
- METIS-312559
- o1-Heavy subgraph

### Cite this

*31*(3), 649-667. DOI: 10.1007/s00373-014-1406-4

}

**Characterizing heavy subgraph pairs for pancyclicity.** / Li, Binlong; Ning, Bo; Broersma, Haitze J.; Zhang, Shenggui.

Research output: Scientific - peer-review › Article

TY - JOUR

T1 - Characterizing heavy subgraph pairs for pancyclicity

AU - Li,Binlong

AU - Ning,Bo

AU - Broersma,Haitze J.

AU - Zhang,Shenggui

N1 - eemcs-eprint-25946

PY - 2015/5

Y1 - 2015/5

N2 - 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.

AB - 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.

KW - EWI-25946

KW - MSC-05C

KW - Pancyclic graph

KW - IR-95792

KW - Forbidden subgraph

KW - Hamiltonian graph

KW - METIS-312559

KW - o1-Heavy subgraph

U2 - 10.1007/s00373-014-1406-4

DO - 10.1007/s00373-014-1406-4

M3 - Article

VL - 31

SP - 649

EP - 667

IS - 3

ER -