Pancyclicity when each cycle contains k chords

Abstract

For integers $n\ge k\ge 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\in \{k,k+1,\dots ,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\ge 2$, $c(n,k)\ge {\Omega }_k(n^{1/k})$ and they asked if $n^{1/k}$ gives the correct order of magnitude of $c(n,k)$ for $k\ge 2$. Our main theorem answers this question as we prove that for every integer $k\ge 2$, and for sufficiently large $n$, $c(n,k)\le k\lceil n^{1/k}\rceil +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}$.

arXiv comment13 Pages

References in corpus (1)

• Minimal Pancyclicity