On the number of edges in some graphs

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:1905.06001

Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 , 283, 751–755, 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
[ Download ] [ 2019-05-12 09:51:21 uploaded by Laichunhui ] [ 867 downloads ] [ 0 comments ]
  • https://doi.org/10.1016/j.dam.2020.03.008
  title={On the number of edges in some graphs},
  author={Lai Chunhui},
  booktitle={Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 },
Lai Chunhui. On the number of edges in some graphs. 2020. Vol. 283. In Discrete Applied Mathematics (2020), https://doi.org/10.1016/j.dam.2020.03.008 . pp.751–755. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20190512095121802105344.
Please log in for comment!
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved