Pancyclicity When Each Cycle Contains k Chords

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
• 05d99
• 11b75