On the size of graphs without repeated cycle lengths

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:1711.06001

Discrete Applied Mathematics, 232, 226-229, 2017.12
In 1975, P. Erd\"{o}s proposed the problem of determining the maximum number $f(n)$ of edges in a graph with $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $$f(n)\geq n+\frac{107}{3}t+\frac{7}{3}$$ for $t=1260r+169 \,\ (r\geq 1)$ and $n \geq \frac{2119}{4}t^{2}+87978t+\frac{15957}{4}$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + \frac{7654}{19071}},$ which is better than the previous bounds $\sqrt 2$ (Shi, 1988), $\sqrt {2.4}$ (Lai, 2003). The conjecture $\lim_{n \rightarrow \infty} {f(n)-n\over \sqrt n}=\sqrt {2.4}$ is not true.
graph, cycle, number of edges
[ Download ] [ 2017-11-07 08:33:35 uploaded by Laichunhui ] [ 1048 downloads ] [ 0 comments ]
  title={On the size of graphs without repeated cycle lengths},
  author={Lai Chunhui},
  booktitle={Discrete Applied Mathematics},
Lai Chunhui. On the size of graphs without repeated cycle lengths. 2017. Vol. 232. In Discrete Applied Mathematics. pp.226-229. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20171107083336050698849.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved