Forbidden Pairs and (k,m)-Pancyclicity

• Autorzy: Charles Brian Crane
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hamiltonian; pancyclic; forbidden subgraph; cycle; claw-free

Kategorie tematyczne

• 05C45: Eulerian and Hamiltonian graphs
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 649-663

Daty

wydano

2017-08-01

otrzymano

2015-07-22

poprawiono

2016-06-03

zaakceptowano

2016-06-04

online

2017-07-06

Twórcy

autor

Charles Brian Crane

• , , 8425 W McNichols Rd, , MI ,

Identyfikatory

DOI

10.7151/dmgt.1949