Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

• Autorzy: Fatima Affif Chaouche , Carrie G. Rutherford , Robin W. Whitty
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

extremal graph theory; pancyclic graph; Hamilton cycle

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 533-539

Daty

wydano

2015-08-01

otrzymano

2014-04-14

poprawiono

2014-11-07

zaakceptowano

2014-11-07

online

2015-07-29

Twórcy

autor

Fatima Affif Chaouche

• University of Sciences and Technology Houari Boumediene Algiers, Algeria

autor

Carrie G. Rutherford

• Faculty of Business London South Bank University London , UK

autor

Robin W. Whitty

• School of Mathematical Sciences Queen Mary University of London London, UK

Bibliografia

• [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]
• [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]
• [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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1818