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

不包含两个相同长度的循环的图形中边数的下限

A LOWER BOUND OF THE NUMBER OF EDGES IN A GRAPH CONTAINING NO TWO CYCLES OF THE SAME LENGTH

摘要: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+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\sb {n \to \infty} {f(n)-n \over \sqrt n} \geq \sqrt {2 + {2562 \over 6911}}.$

英文摘要:

版本历史

[V1] 2022-05-14 19:48:27 chinaXiv:202205.00103V1 下载全文
点击下载全文
同行评议状态
待评议
许可声明
metrics指标
  • 点击量3453
  • 下载量356
评论
分享
邀请专家评阅