2016/12/28 by Vladislav Taranchuk, Taranchuk, Vladislav
Computer Science · Mathematics · #05D99 #11B75 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1612.08802
openalex publication_date 2016/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \lceil n1/k \rceil + 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.