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

Abstract

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

How to cite

top

Fatima 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. [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. [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. [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. [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. [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. [6] S. Griffin, Minimal pancyclicity, preprint, arxiv.org/abs/1312.0274, 2013. 
  7. [7] M.R. Sridharan, On an extremal problem concerning pancyclic graphs, J. Math. Phys. Sci. 12 (1978) 297-306. Zbl0384.05044

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.