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.

  • $\begingroup$ Crossposted on mathoverflow. $\endgroup$ – Marzio De Biasi Feb 11 '14 at 11:20
  • $\begingroup$ By minimal cycle, do you mean the same as induced cycle? $\endgroup$ – Martin Vatshelle Feb 12 '14 at 0:25
  • $\begingroup$ 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). $\endgroup$ – Suresh Venkat Feb 12 '14 at 0:54
  • $\begingroup$ Apologies, I won't do it again -- thanks for filling me in. $\endgroup$ – GMB Feb 12 '14 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)!$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.