# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:1905.06001

Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 , 9, 2020.3
In 1975, P. Erd\H os 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. The sequence $(c_1,c_2,\cdots,c_n)$ is the cycle length distribution of a graph $G$ of order $n$， where $c_i$ is the number of cycles of length $i$ in $G$. Let $f(a_1,a_2,\cdots,$ $a_n)$ denote the maximum possible number of edges in a graph which satisfies $c_i\leq a_i$ where $a_i$ is a nonnegative integer. In 1991, Shi posed the problem of determining $f(a_1,a_2,\cdots,a_n)，$ which extended the problem due to Erd\H os, it is clear that $f(n)=f(1,1,\cdots,1)$. Let $g(n,m)=f(a_1,a_2,\cdots,a_n),$ $a_i=1$ for all $i/m$ be integer, $a_i=0$ for all $i/m$ be not integer. It is clear that $f(n)=g(n,1)$. We prove that $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + \frac{40}{99}},$ which is better than the previous bounds $\sqrt 2$ (Shi, 1988), $\sqrt {2 + \frac{7654}{19071}}$ (Lai, 2017). We show that $\liminf_{n \rightarrow \infty} {g(n,m)-n\over \sqrt \frac{n}{m}} > \sqrt {2.444},$ for all even integers $m$. We make the following conjecture: $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} > \sqrt {2.444}.$
Graph, cycle, number of edges
• https://doi.org/10.1016/j.dam.2020.03.008
@inproceedings{lai2020on,
title={On the number of edges in some graphs},
author={Lai Chunhui},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20190512095121802105344},
booktitle={Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 },
pages={9},
year={2020},
}

Lai Chunhui. On the number of edges in some graphs. 2020. In Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 . pp.9. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20190512095121802105344.