A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:1612.06003

Electronic Journal of Combinatorics, 8, 2001.10
In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph of $n$ vertices in which any two cycles are of different lengths. In this paper, it is proved that $f(n)\geq n+32t-1$ for $t=27720r+169\ (r\geq 1)$ and $n\geq\frac{6911}{16}t^2+\frac{514441}{8}t-\frac{3309665}{16}$ . Consequently, $\liminf_{n\to\infty}\frac{f(n)-n}{\sqrt n}\geq\sqrt{2+\frac{2562}{6911}}$ .
maximum number of edges; cycle; graph
[ Download ] [ 2016-12-27 08:54:53 uploaded by Laichunhui ] [ 776 downloads ] [ 0 comments ] [ Cited by 1 ]
@inproceedings{lai2001a,
  title={A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length},
  author={Lai Chunhui},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227085453346694694},
  booktitle={ Electronic Journal of Combinatorics},
  volume={8},
  year={2001},
}
Lai Chunhui. A Lower Bound for the Number of Edges in a Graph Containing No Two Cycles of the Same Length. 2001. Vol. 8. In Electronic Journal of Combinatorics. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227085453346694694.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved