A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs

Wojciech Wide. "A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 477-499. <http://eudml.org/doc/288027>.

@article{WojciechWide2017,
abstract = {A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ \{3, . . . , n\}. A vertex v ∈ 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-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(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-f1-heavy, if G is H-f1-heavy for every graph H ∈H. Let D denote the deer, a graph consisting of a triangle with two disjoint paths P3 adjoined to two of its vertices. In this paper we prove that every 2-connected \{K1,3, P7, D\}-f1-heavy graph on n ≥ 14 vertices is pancyclic. This result extends the previous work by Faudree, Ryjáček and Schiermeyer.},
author = {Wojciech Wide},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle; Fan-type heavy subgraph; Hamilton cycle; pancyclicity},
language = {eng},
number = {2},
pages = {477-499},
title = {A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs},
url = {http://eudml.org/doc/288027},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Wojciech Wide
TI - A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 477
EP - 499
AB - A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ 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-f1-heavy if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(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-f1-heavy, if G is H-f1-heavy for every graph H ∈H. Let D denote the deer, a graph consisting of a triangle with two disjoint paths P3 adjoined to two of its vertices. In this paper we prove that every 2-connected {K1,3, P7, D}-f1-heavy graph on n ≥ 14 vertices is pancyclic. This result extends the previous work by Faudree, Ryjáček and Schiermeyer.
LA - eng
KW - cycle; Fan-type heavy subgraph; Hamilton cycle; pancyclicity
UR - http://eudml.org/doc/288027
ER -