Authors:
V. Taranchuk
Title:
Pancyclity when each cycle contains k chords
Source:
Discussiones Mathematicae Graph Theory
Received 26.09.2016, Revised 11.12.2017, Accepted 11.12.2017, doi: 10.7151/dmgt.2106

Abstract:
For integers n ≥ k ≥ 2, let c(n,k) be the minimum number of chords that must be added to a cycle of length n so that the resulting graph has the property that for every l ∈{ k , k + 1 , ... , n }, there is a cycle of length l that contains exactly k of the added chords. Affif Chaouche, Rutherford, and Whitty introduced the function c(n,k). They showed that for every integer k ≥ 2, c(n , k ) ≥ Ωk ( n1/k ) and they asked if n1/k gives the correct order of magnitude of c(n, k) for k ≥ 2. Our main theorem answers this question as we prove that for every integer k ≥ 2, and for sufficiently large n, c(n , k) ≤ k ⌈ n1/k ⌉ + k2. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n,k) is n1/k.
Keywords:
pancyclicity, chords

Links:
PDF