Pancyclicity When Each Cycle Contains k Chords

Taranchuk, Vladislav

Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 867-879

Résumé

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². 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.

Détail

Keywords: pancyclicity, chords