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

An old problem of Erdős: a graph without two cycles of the same length

请选择邀稿期刊:

An old problem of Erd?s: a graph without two cycles of the same length

摘要: In 1975, P. Erdős proposed the problem of determining the maximum number $f(n)$ of edges in a graph on $n$ vertices in which any two cycles are of different lengths. Let $f^{\ast}(n)$ be the maximum number of edges in a simple graph on $n$ vertices in which any two cycles are of different lengths. Let $M_n$ be the set of simple graphs on $n$ vertices in which any two cycles are of different lengths and with the edges of $f^{\ast}(n)$. Let $mc(n)$ be the maximum cycle length for all $G \in M_n$. In this paper, it is proved that for $n$ sufficiently large, $mc(n)\leq \frac{15}{16}n$. We make the following conjecture: $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$

版本历史

[V2] 2024-02-18 12:06:55 ChinaXiv:202307.00026v2 查看此版本 下载全文
[V1] 2023-07-05 08:11:03 ChinaXiv:202307.00026V1 下载全文
点击下载全文
预览
同行评议状态
通过
许可声明
metrics指标
  •  点击量4251
  •  下载量212
评论
分享