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.$$
| [V1] | 2023-07-05 08:11:03 | ChinaXiv:202307.00026V1 | 下载全文 |
相关信息
通过
点击量
下载量
