Characterizing heavy subgraph pairs for pancyclicity

Binlong Li, Bo Ning, Haitze J. Broersma, Shenggui Zhang

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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 languageUndefined
Pages (from-to)649-667
Number of pages19
JournalGraphs and combinatorics
Volume31
Issue number3
DOIs
Publication statusPublished - May 2015

Keywords

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

Cite this