Some extremal problems on graph theory

Lai Chunhui Minnan Normal University

Combinatorics mathscidoc: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
[ Download ] [ 2021-08-21 09:29:27 uploaded by Laichunhui ] [ 189 downloads ] [ 0 comments ]
  • 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.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved