Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 3 down vote favorite

I would like to ask if anybody knows any result on the least number of edges the maximum simple cycle of connected cubic bridgeless graphs, must have. Thanks

share|improve this question

1 Answer

up vote 4 down vote accepted

So you are looking for the circumference of a connected cubic bridgeless graph $G$. Since a bridgeless cubic graph is immediately 2-connected, Bondy and Entringer showed in the paper

Longest cycles in 2-connected graphs with prescribed maximum degree, Canadian Journal of Mathematics, 1980,

that $G$ contains a cycle of length at least $4 (\log_2 n - \log_2\log_2 n - 5)$. And a graph which meets the bound is provided in the result Über längste Kreise in regulären Graphen by Lang and Walther, so this is the best possible.

For the reference, see Longest cycles in 3-connected cubic graphs by Bill Jackson. If the graph is 3-connected, then the bound can be improved to $\Omega(n^c)$ with $c\approx 0.69$, and there are efficient algorithm approximately finding a long cycle in $G$.

share|improve this answer
Hsien-Chih the bound you provide is negative for n<256, so for most practical graphs – N27 Jan 10 '11 at 3:12
@N27: Oops so you need a bound for small size graphs. Maybe you can put the requirement in your question, and there may be someone who knows the answer. (I have no idea what the bound is when the graph is small, it seems like the result above is for sufficiently large n.) – Hsien-Chih Chang 張顯之 Jan 10 '11 at 3:29
@Hsien-Chih There is something wrong with this bound obviously, since for 100,000 vertices it gives a cycle of length 30. Maybe they refer to something else in their publication. However, this problem doesn't seem trivial. – N27 Jan 10 '11 at 3:33
@N27: I'm not sure if the bound is wrong. There are cubic bridgeless graphs with a large number of nodes with small maximum cycle. Take this graph for example. (This graph may not meet our bound, but it gives intuition.) – Hsien-Chih Chang 張顯之 Jan 10 '11 at 3:50
1  
@ Hsien-Chih Chang, actually I learned what I wanted from the example of Dr. Eppstein, since what I needed was a counterexample of a cubic bridgeless graph with a max simple cycle of less than n/2 vertices. – N27 Jan 12 '11 at 5:31
show 3 more comments

Your Answer

 
discard

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

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