How many minimal $k$-cycles can you put in a graph?

I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$. What is known about this problem? How many cycles can I squeeze in?

Additionally, how does the problem change if I require that my graph has $\ge m$ edges?

Clarification: I care purely about the existence of a many-cycled graph; it doesn't need to be efficiently constructable.

• Crossposted on mathoverflow. Feb 11, 2014 at 11:20
• By minimal cycle, do you mean the same as induced cycle? Feb 12, 2014 at 0:25
• I see there's already an answer here, which is great. However, our policy is not to allow simultaneous cross posting (you can cross post after a day or two if you're not getting the answer you want). Feb 12, 2014 at 0:54
• Apologies, I won't do it again -- thanks for filling me in.
– GMB
Feb 12, 2014 at 4:07

If $k$ is divisible by 2 we can take a clique on $n/2$ vertices and subdivide each edge once. This graph will have ${n/2 \choose k/2} \cdot (k/2-1)!/2$ cycles of length $k$.
Hence the total number of cycles is $\frac{1}{2} \sum_{i=k/2}^{i=n/2} {n/2 \choose i} \cdot (i-1)!$