Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 –  Gerhard Paseman Oct 3 '13 at 18:16
1  
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 –  Boris Bukh Oct 3 '13 at 18:20
    
The related integer sequence appears to be $4,12,24,40,40,96,96$ –  Jernej Oct 3 '13 at 23:21
    
@Jernej: Agreed if you count oriented cycles. I'm posting counts for unoriented cycles. –  Brendan McKay Oct 4 '13 at 2:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.