FORBIDDEN PAIRS AND (k, m)-PANCYCLICITY

作者：Crane Charles Brian^*

来源：Discussiones Mathematicae - Graph Theory, 2017, 37(3): 649-663.

DOI：10.7151/dmgt.1949

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

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 is an element of {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.

• 出版日期2017-8