# Forbidden Pairs and (k,m)-Pancyclicity

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

top

## Abstract

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

## How to cite

top

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 -

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.