• 1 Citations

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
StatePublished - May 2015

Fingerprint

Terminology
Ores

Keywords

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

Cite this

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

In: Graphs and combinatorics, Vol. 31, No. 3, 05.2015, p. 649-667.

Research output: Scientific - peer-reviewArticle

@article{f5ecc09800ed48e18f1d58a870587601,
title = "Characterizing heavy subgraph pairs for pancyclicity",
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.",
keywords = "EWI-25946, MSC-05C, Pancyclic graph, IR-95792, Forbidden subgraph, Hamiltonian graph, METIS-312559, o1-Heavy subgraph",
author = "Binlong Li and Bo Ning and Broersma, {Haitze J.} and Shenggui Zhang",
note = "eemcs-eprint-25946",
year = "2015",
month = "5",
doi = "10.1007/s00373-014-1406-4",
volume = "31",
pages = "649--667",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer Japan",
number = "3",

}

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

In: Graphs and combinatorics, Vol. 31, No. 3, 05.2015, p. 649-667.

Research output: Scientific - peer-reviewArticle

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

JO - Graphs and combinatorics

T2 - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 3

ER -