Graphs without repeated cycle lengths

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:1702.06001

Australasian Journal of Combinatorics, 27, 101-105, 2003.3
In 1975, P. Erd\"{o}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+36t$$ for $t=1260r+169 \,\ (r\geq 1)$ and $n \geq 540t^{2}+\frac{175811}{2}t+\frac{7989}{2}$. Consequently, $\liminf\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2 \over 5}},$ which is better than the previous bounds $\sqrt 2$ (see [2]), $\sqrt {2+{2562\over 6911}}$ (see [7]).
graph, cycle, number of edges
[ Download ] [ 2017-02-12 08:58:48 uploaded by Laichunhui ] [ 123 downloads ] [ 0 comments ]
@inproceedings{lai2003graphs,
  title={GRAPHS WITHOUT REPEATED CYCLE LENGTHS},
  author={Lai Chunhui},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170212085848919414434},
  booktitle={Australasian Journal of Combinatorics},
  volume={27},
  pages={101-105},
  year={2003},
}
Lai Chunhui. GRAPHS WITHOUT REPEATED CYCLE LENGTHS. 2003. Vol. 27. In Australasian Journal of Combinatorics. pp.101-105. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170212085848919414434.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved