Some open problems on cycles

MaRDI QIDQ2940108zbMATH OpenFDO

Authors Chunhui Lai, Mingjing Liu

Publication date 26 January 2015

Full work available at URL https://arxiv.org/abs/1110.1144

zbMATH Keywords

cycleeven graphTuran numbermaximum number of edgesHajós conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Hajos' conjecture that every simple even graph on $n$ vertices can be decomposed into at most $(n-1)/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). Let $f(n)$ be the maximum number of edges in a graph on $n$ vertices in which no two cycles have the same length. P. 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. P. Erdos conjectured that there exists a positive constant $c$ such that $ex(n,C_{2k})geqc{n}^{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). This paper summarizes some results on these problems and the conjectures that relate to these. We do not think Haj'{o}s conjecture is true.

Recommendations

• An old problem of Erdős: a graph without two cycles of the same length
• Extremal problems for cycles in graphs
• On maximum cycle-distributed graphs
• Hajós' conjecture and small cycle double covers of planar graphs
• On the number of edges in some graphs

Cited in

(5)

• On the number of edges in some graphs
• An old problem of Erdős: a graph without two cycles of the same length
• scientific article; zbMATH DE number 4133532 (Why is no real title available?)
• On the size of graphs without repeated cycle lengths
• scientific article; zbMATH DE number 3997134 (Why is no real title available?)

This page was built for publication: Some open problems on cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940108)