Abstract
Let $G$ be an $n$-vertex graph obtained by adding chords to a cycle of length
$n$. Markstr\"{o}m asked for the maximum number of edges in $G$ if there are no
two cycles in $G$ with the same length. A simple counting argument shows that
such a graph can have at most $n + \sqrt{2n} +1 $ edges. Using difference sets
in $\mathbb{Z}_n$, we show that for infinitely many $n$, there is an $n$-vertex
Hamiltonian graph with $n + \sqrt{n - 3/4} - 3/2$ edges and no repeated cycle
length.