Geodesic
A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 477-499.

Voir la notice de l'article provenant de la source Library of Science

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 ℋ we say that G is ℋ-f1-heavy, if G is H-f1-heavy for every graph 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.
Keywords: cycle, Fan-type heavy subgraph, Hamilton cycle, pancyclicity 
@article{DMGT_2017_37_2_a11,
     author = {Wide, Wojciech},
     title = {A {Triple} of {Heavy} {Subgraphs} {Ensuring} {Pancyclicity} of {2-Connected} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {477--499},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a11/}
}
TY  - JOUR
AU  - Wide, Wojciech
TI  - A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 477
EP  - 499
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a11/
LA  - en
ID  - DMGT_2017_37_2_a11
ER  - 
%0 Journal Article
%A Wide, Wojciech
%T A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 477-499
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a11/
%G en
%F DMGT_2017_37_2_a11
Wide, Wojciech. A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 477-499. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a11/

[1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamil- tonicity (PhD Thesis, Memphis State University, USA, 1991).

[2] P. Bedrossian, G. Chen and R.H. Schelp, A generalization of Fan’s condition for Hamiltonicity, pancyclicity and Hamiltonian connectedness, Discrete Math. 115 (1993) 39-59. doi: 10.1016/0012-365X(93)90476-A

[3] A. Benhocine and A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs, J. Combin. Theory Ser. B 58 (1987) 167-180. doi: 10.1016/0095-8956(87)90038-4

[4] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1971) 80-84. doi: 10.1016/0095-8956(71)90016-5

[5] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan London and Elsevier, 1976). doi: 10.1007/978-1-349-03521-2

[6] G. Chen, B. Wei and X. Zhang, Degree light-free graphs and Hamiltonian cycles, Graphs Combin. 17 (2001) 409-434. doi: 10.1007/s003730170018

[7] R. Faudree, Z. Ryjáˇcek and I. Schiermeyer, Forbidden subgraphs and cycle extend- ability, J. Combin. Math. Combin. Comput. 19 (1995) 109-128.

[8] M. Ferrara, M.S. Jacobson and A. Harris, Cycle lengths in Hamiltonian graphs with a pair of vertices having large degree sum, Graphs Combin. 26 (2010) 215-223. doi: 10.1007/s00373-010-0915-z

[9] B. Ning, Fan-type degree condition restricted to triples of induced subgraphs ensuring Hamiltonicity, Inform. Process. Lett. 113 (2013) 823-826. doi: 10.1016/j.ipl.2013.07.014

[10] B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014) 127-136.

[11] E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for Hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988) 99-107. doi: 10.1016/0095-8956(88)90058-5

[12] W.Wide l, A Fan-type heavy pair of subgraphs for pancyclicity of 2-connected graphs, Discuss. Math. Graph Theory 36 (2016) 173-184. doi: 10.7151/dmgt.1840