Geodesic
Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 533-539.

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

It is known that Θ(log n) chords must be added to an n-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, Θ(n) chords are required. A possibly ‘intermediate’ variation is the following: given k, 1 ≤ k ≤ n, how many chords must be added to ensure that there exist cycles of every possible length each of which passes exactly k chords? For fixed k, we establish a lower bound of Ω(n1/k) on the growth rate.
Keywords: extremal graph theory, pancyclic graph, Hamilton cycle 
@article{DMGT_2015_35_3_a10,
     author = {Affif Chaouche, Fatima and Rutherford, Carrie G. and Whitty, Robin W.},
     title = {Pancyclicity when each {Cycle} {Must} {Pass} {Exactly} k {Hamilton} {Cycle} {Chords}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {533--539},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a10/}
}
TY  - JOUR
AU  - Affif Chaouche, Fatima
AU  - Rutherford, Carrie G.
AU  - Whitty, Robin W.
TI  - Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 533
EP  - 539
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a10/
LA  - en
ID  - DMGT_2015_35_3_a10
ER  - 
%0 Journal Article
%A Affif Chaouche, Fatima
%A Rutherford, Carrie G.
%A Whitty, Robin W.
%T Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 533-539
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a10/
%G en
%F DMGT_2015_35_3_a10
Affif Chaouche, Fatima; Rutherford, Carrie G.; Whitty, Robin W. Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 533-539. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a10/

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

[2] J.A. Bondy, Pancyclic graphs: recent results, infinite and finite sets, in : Colloq. Math. Soc. János Bolyai, Keszthely, Hungary (1973) 181-187.

[3] H.J. Broersma, A note on the minimum size of a vertex pancyclic graph, Discrete Math. 164 (1997) 29-32. doi:10.1016/S0012-365X(96)00040-4

[4] R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey and D.E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996) 329-359. doi:10.1007/BF02124750

[5] J.C. George, A.M. Marr and W.D. Wallis, Minimal pancyclic graphs, J. Combin. Math. Combin. Comput. 86 (2013) 125-133.

[6] S. Griffin, Minimal pancyclicity, preprint, arxiv.org/abs/1312.0274, 2013.

[7] M.R. Sridharan, On an extremal problem concerning pancyclic graphs, J. Math. Phys. Sci. 12 (1978) 297-306.