On the number of edges in some graphs

Abstract

In 1975, P. Erdő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. 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\le 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ős, 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 ${\mathrm{liminf}}_{n\to \infty }\frac{f(n)-n}{\sqrt{n}}\ge \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 ${\mathrm{liminf}}_{n\to \infty }\frac{g(n,m)-n}{\sqrt{\frac{n}{m}}}>\sqrt{2.444},$ for all even integers $m$. We make the following conjecture: ${\mathrm{liminf}}_{n\to \infty }\frac{f(n)-n}{\sqrt{n}}>\sqrt{2.444}.$

9 pages

References in corpus (1)

• On the size of graphs without repeated cycle lengths

Cited by in corpus (2)

• Non-repeated cycle lengths and Sidon sequences
• An old problem of Erdős: a graph without two cycles of the same length