Forbidden Pairs and (k,m)-Pancyclicity

Charles Brian Crane. "Forbidden Pairs and (k,m)-Pancyclicity." Discussiones Mathematicae Graph Theory 37.3 (2017): 649-663. <http://eudml.org/doc/288394>.

@article{CharlesBrianCrane2017,
abstract = {A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ \{m, m+1, . . . , n\}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs \{R, S\}, we determine the smallest value m such that any 2-connected \{R, S\}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.},
author = {Charles Brian Crane},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamiltonian; pancyclic; forbidden subgraph; cycle; claw-free},
language = {eng},
number = {3},
pages = {649-663},
title = {Forbidden Pairs and (k,m)-Pancyclicity},
url = {http://eudml.org/doc/288394},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Charles Brian Crane
TI - Forbidden Pairs and (k,m)-Pancyclicity
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 649
EP - 663
AB - A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs {R, S}, we determine the smallest value m such that any 2-connected {R, S}-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.
LA - eng
KW - hamiltonian; pancyclic; forbidden subgraph; cycle; claw-free
UR - http://eudml.org/doc/288394
ER -