您当前的位置: > 详细浏览

On the size of graphs without repeated cycle lengths

请选择邀稿期刊:
摘要: In 1975, P. Erd {o}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. In this paper, it is proved that $$f(n) geq n+ frac{107}{3}t+ frac{7}{3}$$
 for $t=1260r+169  ,  (r geq 1)$
 and $n  geq  frac{2119}{4}t^{2}+87978t+ frac{15957}{4}$. Consequently,
$ liminf sb {n  to  infty} {f(n)-n  over  sqrt n}  geq  sqrt {2 +
frac{7654}{19071}},$   which is better than the previous bounds
$ sqrt 2$  Y. Shi, Discrete Math. 71(1988), 57-71 , $ sqrt {2.4}$
    C. Lai,  Australas. J. Combin. 27(2003), 101-105 .
   The conjecture $ lim_{n  rightarrow  infty} {f(n)-n over  sqrt n}= sqrt {2.4}$ is not true.

版本历史

[V2] 2024-03-26 18:22:32 ChinaXiv:202205.00107V2 下载全文
[V1] 2022-05-15 10:42:22 ChinaXiv:202205.00107v1 查看此版本 下载全文
点击下载全文
预览
同行评议状态
通过
许可声明
metrics指标
  •  点击量6939
  •  下载量681
评论
分享