Pancyclicity when each cycle must pass exactly $k$ Hamilton cycle chords

Abstract

It is known that $\Theta (\log n)$ chords must be added to an $n$-cycle to produce a pancyclic graph; for vertex pancyclicity, where every vertex belongs to a cycle of every length, $\Theta (n)$ chords are required. A possibly `intermediate' variation is the following: given $k$, $1\le k\le n$, how many chords must be added to ensure that there exist cycles of every length each of which passes exactly $k$ chords? For fixed $k$, we establish a lower bound of $\Omega \left(n^{1/k}\right)$ on the growth rate.