On the size of graphs with all cycle having distinct length

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:1612.06002

Discrete Mathematics, 122, 363-364, 1993.12
Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. In 1975, Erdős raised the question of determining $f(n)$ [see J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New York, 1976; MR0411988 (54 #117)]. We prove that for $n\geq 36\cdot 5t^2-4\cdot 5t+1$ one has $f(n)\geq n+9t-1$ . We conjecture that $\liminf (f(n)-n)/\sqrt n\leq\sqrt 3$ .
maximum number of edges; graph; cycle
[ Download ] [ 2016-12-27 08:43:59 uploaded by Laichunhui ] [ 653 downloads ] [ 0 comments ] [ Cited by 5 ]
@inproceedings{lai1993on,
  title={On the size of graphs with all cycle having distinct length},
  author={Lai Chunhui},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227084359716230693},
  booktitle={Discrete Mathematics},
  volume={122},
  pages={363-364},
  year={1993},
}
Lai Chunhui. On the size of graphs with all cycle having distinct length. 1993. Vol. 122. In Discrete Mathematics. pp.363-364. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20161227084359716230693.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved