Graphs without repeated cycle lengths

Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2025-07-09

Chunhui Lai

Abstract： In 1975, P. Erd\"{o}s proposed the problem of determining the
maximum number $f(n)$ of edges in a  graph of $n$ vertices in
which any two cycles are of different
 lengths. In this paper, it is proved that $$f(n)\geq n+36t$$ for $t=1260r+169 \,\ (r\geq 1)$
 and $n \geq 540t^{2}+\frac{175811}{2}t+\frac{7989}{2}$. Consequently,
$\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 +
{2 \over 5}},$   which is better than the previous bounds $\sqrt
2$ (see [2]), $\sqrt {2+{2562\over 6911}}$
  (see [7]).
  \par
  Combining this with Boros, Caro, F\"uredi and Yuster’s upper bound, we get
  $$1.98\geq \limsup_{n \rightarrow \infty} {f(n)-n\over \sqrt n} \geq
  \liminf_{n \rightarrow \infty} {f(n)-n\over \sqrt n}\geq \sqrt {2.4}.$$
  \par

YES

 Hits 127  Downloads 18  Comment 0