# Forbidden Pairs and (k,m)-Pancyclicity

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 3, page 649-663
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topCharles 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.