PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 3 | 533-539
Tytuł artykułu

Pancyclicity when each Cycle Must Pass Exactly k Hamilton Cycle Chords

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
35
Numer
3
Strony
533-539
Opis fizyczny
Daty
wydano
2015-08-01
otrzymano
2014-04-14
poprawiono
2014-11-07
zaakceptowano
2014-11-07
online
2015-07-29
Twórcy
  • University of Sciences and Technology Houari Boumediene Algiers, Algeria, affif@yahoo.fr
  • School of Mathematical Sciences Queen Mary University of London London, UK, r.whitty@qmul.ac.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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1818
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.