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
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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$.
answered Jan 10, 2011 at 2:58
-
$\begingroup$ Hsien-Chih the bound you provide is negative for n<256, so for most practical graphs $\endgroup$– N27Commented Jan 10, 2011 at 3:12
-
$\begingroup$ @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.) $\endgroup$ Commented Jan 10, 2011 at 3:29
-
$\begingroup$ @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. $\endgroup$– N27Commented Jan 10, 2011 at 3:33
-
$\begingroup$ @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.) $\endgroup$ Commented Jan 10, 2011 at 3:50
-
1$\begingroup$ @ 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. $\endgroup$– N27Commented Jan 12, 2011 at 5:31