# MathSciDoc: An Archive for Mathematician ∫

#### Combinatoricsmathscidoc:2108.06001

The 22nd Conference of the International Federation of Operational Research Societies, 2021.8
Let \$f(n)\$ be the maximum number of edges in a graph on \$n\$ vertices in which no two cycles have the same length. In 1975, Erdos raised the problem of determining \$f(n)\$ (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). Given a graph \$H\$, what is the maximum number of edges of a graph with \$n\$ vertices not containing \$H\$ as a subgraph? This number is denoted \$ex(n,H)\$, and is known as the Turan number. Erdos conjectured that there exists a positive constant \$c\$ such that \$ex(n,C_{2k})\geq cn^{1+1/k}\$(see P. Erdos, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) , pp. 97--109, Academic Press, London, 1971). Haj\'{o}s conjectured that every simple even graph on \$n\$ vertices can be decomposed into at most \$n/2\$ cycles (see L. Lovasz, On covering of graphs, in: P. Erdos, G.O.H. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 231 - 236 ). We present the problems, conjectures related to these problems and we summarize the know results.
graph, Cycles, number of edges, circuit decomposition, Turan number
• https://www.ifors2021.kr/
```@inproceedings{lai2021some,
title={Some extremal problems on graph theory},
author={Lai Chunhui},
url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210821092927648300859},
booktitle={The 22nd Conference of the International Federation of Operational Research Societies},
year={2021},
}
```
Lai Chunhui. Some extremal problems on graph theory. 2021. In The 22nd Conference of the International Federation of Operational Research Societies. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20210821092927648300859.