An old problem of Erd\H os: a graph without two cycles of the same length

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc:2110.06001

Discrete Applied Mathematics, 337, 42-45, 2023.10
In 1975, P. Erd\H os 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.$ \par We make the following conjecture: \par \bigskip \noindent{\bf Conjecture.} $$\lim_{n \rightarrow \infty} {mc(n)\over n}= 0.$$
graph, cycle, number of edges
[ Download ] [ 2021-10-13 14:26:26 uploaded by Laichunhui ] [ 836 downloads ] [ 0 comments ]
@inproceedings{lai2023an,
  title={An old problem of Erd\H os: a graph without two cycles of the same length},
  author={Lai Chunhui},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20211013142626071808877},
  booktitle={Discrete Applied Mathematics},
  volume={337},
  pages={42-45},
  year={2023},
}
Lai Chunhui. An old problem of Erd\H os: a graph without two cycles of the same length. 2023. Vol. 337. In Discrete Applied Mathematics. pp.42-45. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20211013142626071808877.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved