# Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

Fatima Affif Chaouche; Carrie G. Rutherford; Robin W. Whitty

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 533-539
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topFatima Affif Chaouche, Carrie G. Rutherford, and Robin W. Whitty. "Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords." Discussiones Mathematicae Graph Theory 35.3 (2015): 533-539. <http://eudml.org/doc/271240>.

@article{FatimaAffifChaouche2015,

abstract = {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.},

author = {Fatima Affif Chaouche, Carrie G. Rutherford, Robin W. Whitty},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {extremal graph theory; pancyclic graph; Hamilton cycle},

language = {eng},

number = {3},

pages = {533-539},

title = {Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords},

url = {http://eudml.org/doc/271240},

volume = {35},

year = {2015},

}

TY - JOUR

AU - Fatima Affif Chaouche

AU - Carrie G. Rutherford

AU - Robin W. Whitty

TI - Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 533

EP - 539

AB - 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.

LA - eng

KW - extremal graph theory; pancyclic graph; Hamilton cycle

UR - http://eudml.org/doc/271240

ER -

## References

top- [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] Zbl0183.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] Zbl0871.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] Zbl0863.65008
- [5] J.C. George, A.M. Marr and W.D. Wallis, Minimal pancyclic graphs, J. Combin. Math. Combin. Comput. 86 (2013) 125-133. Zbl1314.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. Zbl0384.05044

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.