Graphs without repeated cycle lengths

分类： 数学 >> 离散数学和组合数学 提交时间： 2025-07-09

ChunhuiLAI

摘要： In 1975, P. Erd\"{o}s proposed the problem of determining themaximum number $f(n)$ of edges in a graph of $n$ vertices inwhich any two cycles are of differentlengths. 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 $\sqrt2$ (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

通过

 点击量 122  下载量 17  评论 0