A note on the number of edges in a Hamiltonian graph with no repeated cycle length

Abstract

Let $G$ be an $n$-vertex graph obtained by adding chords to a cycle of length $n$. Markströ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.

Cited by in corpus (1)

• An old problem of Erdős: a graph without two cycles of the same length