Some unsolved problems on cycles

Details Some unsolved problems on cycles Some unsolved problems on cycles

2011-10-06

arxiv.org/abs/1110.1144v2

Mathematics

Combinatorics

10 pages

Scientific paper

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})\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). This paper summarizes some results on these problems and the conjectures that relate to these. It seems to us that Haj\'{o}s conjecture is false.

Affiliated with

Also associated with

No associations

Rating

Some unsolved problems on cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some unsolved problems on cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some unsolved problems on cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180806