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

Abstract

In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast }(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast }(n)$. Let $mc(n)$ be the maximum cycle length for all $G\in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\le \frac{15}{16}n$. We make the following conjecture: $$\underset{n\to \infty }{\lim }\frac{mc(n)}{n}=0.$$

6 pages

References in corpus (1)

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