From: israel@math.ubc.ca (Robert Israel) Subject: Re: How many cycles in a graph ? Date: 3 Mar 1999 19:46:44 GMT Newsgroups: sci.math Keywords: bounds for the number of cycles in a planar graph In article <36DD53C3.FF03C52B@informatik.uni-freiburg.de>, Christoph Dornheim writes: |> since I am concerned with planar graphs I am wondering |> if there are known and provable 'small' upper bounds for the |> number of cycles of a given graph. |> A certain bound is the size of the cycle space, which |> is exponential in the number of vertices. But are there |> any better bounds for arbitrary graphs ? |> And in the special case of planar graphs: are there any |> theorems stating a smaller bound on the number of cycles |> in a planar graph than only 2^n ? There can't be an upper bound that's very much smaller. Consider a planar graph that looks like this, with vertices at the *'s: _____________ / \ *---*---*---*---* \ / \ / \ / \ / * * * * with 2n-1 vertices, n in the top layer and n-1 in the bottom layer. There are more than 2^(n-1) cycles here: consider a path that starts at the leftmost vertex, goes to the rightmost (choosing either the top or bottom route in each triangle) and then back on the top edge. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: How many cycles in a graph ? Date: 3 Mar 1999 11:53:11 -0800 Newsgroups: sci.math In <36DD53C3.FF03C52B@informatik.uni-freiburg.de> Christoph Dornheim writes: > And in the special case of planar graphs: are there any > theorems stating a smaller bound on the number of cycles > in a planar graph than only 2^n ? It is not possible to prove smaller bounds than 2^n, because the number is larger than 2^n. There is a paper in WG '97 (Graph-Theoretic Concepts in Computer Science. 23rd International Workshop, WG'97. Proceedings, Berlin, Germany, 18-20 June 1997, published in the Springer Lecture Notes in Computer Science series), "On the number of simple cycles in planar graphs", by Alt, Fuchs, and Kriegel, proving upper bounds of 3.364^n and lower bounds of 2.2773^n. I worked on this problem some with Marek Chrobak, but never published anything. We got a worse upper bound but a slightly better lower bound: 2.278^n simple cycles in a graph formed by stacking square antiprisms. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/