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.

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

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .