I was curious if there was a reference which answers the question, What is the maximum number of edges in a graph $G$ with $n$ vertices which does not contain a $5$-cycle? $k$-cycle? The analogous question for $k=4$ is well known.
1
-
$\begingroup$ The easiest way to avoid a particular odd cycle is if the graph is bipartite. See mathoverflow.net/questions/4810/… $\endgroup$– Douglas ZareCommented Jan 19, 2016 at 6:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For cycles of odd length, the only extremal graphs for large $n$ are complete bipartite graphs with the sides as equal as possible. For smaller $n$ there can be other extremal graphs. The complete story was worked out fairly recently by Füredi and Gunderson.
Cycles of even length are much harder. Some references are given in this paper and more in this paper. See this paper too. Basically there are lots of partial results but the exact general solution is out of reach.
answered Jan 19, 2016 at 7:32