A TRIPLE OF HEAVY SUBGRAPHS ENSURING PANCYCLICITY OF 2-CONNECTED GRAPHS

作者：Widel Wojciech^*

来源：Discussiones Mathematicae - Graph Theory, 2017, 37(2): 477-500.

DOI：10.7151/dmgt.1938

• cycle
• Fan-type heavy subgraph
• Hamilton cycle
• pancyclicity

A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k is an element of{3, . . . , n}. A vertex v is an element of V (G) is called super-heavy if the number of its neighbours in G is at least (n + 1)/2. For a given graph H we say that G is H-f(1)-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v is an element of V (K), d(K)(u, v) = 2 implies that at least one of them is super-heavy. For a family of graphs H we say that G is H-f(1)-heavy, if G is H-f(1)-heavy for every graph H is an element of H.
Let D denote the deer, a graph consisting of a triangle with two disjoint paths P-3 adjoined to two of its vertices. In this paper we prove that every 2-connected {K-1,K-3, P-7, D}-f(1)-heavy graph on n >= 14 vertices is pancyclic. This result extends the previous work by Faudree, Ryjacek and Schiermeyer.

• 出版日期2017