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$
4
  • $\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$ Oct 3, 2013 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, 2013 at 18:20
  • $\begingroup$ The related integer sequence appears to be $4,12,24,40,40,96,96$ $\endgroup$
    – Jernej
    Oct 3, 2013 at 23:21
  • $\begingroup$ @Jernej: Agreed if you count oriented cycles. I'm posting counts for unoriented cycles. $\endgroup$ Oct 4, 2013 at 2:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.