Geodesic
Pancyclicity When Each Cycle Contains k Chords
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 867-879.

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

For integers n ≥ k ≥ 2, let c(n, k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈ k, k + 1, . . ., n, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function c(n, k). They showed that for every integer k ≥ 2, c(n, k) ≥ Ωk(n1/k) and they asked if n1/k gives the correct order of magnitude of c(n, k) for k ≥ 2. Our main theorem answers this question as we prove that for every integer k ≥ 2, and for sufficiently large n, c(n, k) ≤ k⌈n1/k⌉ + k2. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n, k) is n1/k.
Keywords: pancyclicity, chords 
@article{DMGT_2019_39_4_a7,
     author = {Taranchuk, Vladislav},
     title = {Pancyclicity {When} {Each} {Cycle} {Contains} k {Chords}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {867--879},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a7/}
}
TY  - JOUR
AU  - Taranchuk, Vladislav
TI  - Pancyclicity When Each Cycle Contains k Chords
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 867
EP  - 879
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a7/
LA  - en
ID  - DMGT_2019_39_4_a7
ER  - 
%0 Journal Article
%A Taranchuk, Vladislav
%T Pancyclicity When Each Cycle Contains k Chords
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 867-879
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a7/
%G en
%F DMGT_2019_39_4_a7
Taranchuk, Vladislav. Pancyclicity When Each Cycle Contains k Chords. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 867-879. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a7/

[1] F. Affif Chaouche, C. Rutherford and R. Whitty, Pancyclicity when each cycle must pass exactly k Hamilton cycle chords, Discuss. Math. Graph Theory 35 (2015) 533–539. doi:10.7151/dmgt.1818

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

[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] J.C. George, A. Khodkar and W.D. Wallis, Pancyclic and Bipancyclic Graphs, 1st Ed. (Springer Briefs in Mathematics, Springer, 2016).

[5] S. Griffin, Minimal pancyclicity . arXiv: 1312.0274v1 1 Dec 2013.

[6] D.B. West, Introduction to Graph Theory, 2nd Edition (Pearson Education, Inc., 2001).