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.
@article{bwmeta1.element.doi-10_7151_dmgt_1818,
author = {Fatima Affif Chaouche and Carrie G. Rutherford and Robin W. Whitty},
title = {Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {533-539},
zbl = {1317.05098},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1818}
}
Fatima Affif Chaouche; Carrie G. Rutherford; Robin W. Whitty. Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 533-539. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1818/
[1] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1971) 80-84. doi:10.1016/0095-8956(71)90016-5[Crossref] | Zbl 0183.52301
[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[Crossref] | Zbl 0871.05034
[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[Crossref] | Zbl 0863.65008
[5] J.C. George, A.M. Marr and W.D. Wallis, Minimal pancyclic graphs, J. Combin. Math. Combin. Comput. 86 (2013) 125-133. | Zbl 1314.05102
[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. | Zbl 0384.05044