×

On the number of simple cycles in planar graphs. (English) Zbl 0886.05082

Möhring, Rolf H. (ed.), Graph-theoretic concepts in computer science. 23rd international workshop, WG ’97, Berlin, Germany, June 18–20, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1335, 15-24 (1997).
Summary: Let \(C(G)\) denote the number of simple cycles of a graph \(G\) and let \(C(n)\) be the maximum of \(C(G)\) over all planar graphs with \(n\) nodes. We present a lower bound on \(C(n)\) constructing graphs with at least \(2.27^n\) cycles. Applying some probabilistic arguments we prove an upper bound of \(3.37^n\). We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colorable triangulated graphs.
For the entire collection see [Zbl 0877.00011].

MSC:

05C30 Enumeration in graph theory
05C38 Paths and cycles
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite