11
$\begingroup$

Given a simple cubic graph with $n$ vertices (which implies that $n$ is even), what is a good upper bound on the number of cycles of length $n/2$ it can have?

A random cubic graph has $\Theta((4/3)^n/n)$ cycles of length $n/2$, if I did my sums right. So do random cubic bipartite graphs. Also the whole cycle space has size $2^{n/2+1}$, so twice that is a (silly) upper bound.

Where's the truth?

ADDED: Counts for n=4,6,...,24: 0,2,6,12,20,20,48,48,132,118,312 (not in OEIS). All these are unique except that for 20 vertices there are two graphs.

$\endgroup$
  • $\begingroup$ How about (3n/2) choose (n/2)? Another silly bound, but it might lead somewhere. You could also divide the graph into connected groups of 5 edges and note that a cycle can intersect each group of edges in only 8 ways. (I assume each group is acyclic, perhaps a bad move.) Gerhard "Spins Me Round Right Round" Paseman, 2013.10.03 $\endgroup$ – Gerhard Paseman Oct 3 '13 at 18:16
  • 2
    $\begingroup$ Interesting question! I communicated it to Michael Krivelevich. He does not know, but suggests that the methods from ams.org/mathscinet-getitem?mr=2520275 might be useful $\endgroup$ – Boris Bukh Oct 3 '13 at 18:20
  • $\begingroup$ The related integer sequence appears to be $4,12,24,40,40,96,96$ $\endgroup$ – Jernej Oct 3 '13 at 23:21
  • $\begingroup$ @Jernej: Agreed if you count oriented cycles. I'm posting counts for unoriented cycles. $\endgroup$ – Brendan McKay Oct 4 '13 at 2:02

Your Answer

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

Browse other questions tagged or ask your own question.