Czasopismo
Tytuł artykułu
Autorzy
Warianty tytułu
Języki publikacji
Abstrakty
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
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
649-663
Opis fizyczny
Daty
wydano
2017-08-01
otrzymano
2015-07-22
poprawiono
2016-06-03
zaakceptowano
2016-06-04
online
2017-07-06
Twórcy
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1949