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} ( n^{1/k} ) and they asked if n^{1/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 ⌈ n^{1/k} ⌉ + k^{2}. This upper bound, together with the lower bound of Affif Chaouche et al., shows that the order of magnitude of c(n,k) is n^{1/k}. | |
Keywords: pancyclicity, chords | |
Links: |