Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T09:46:36.822Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Number of Simple Cycles in Planar Graphs

Published online by Cambridge University Press:  01 September 1999

HELMUT ALT ,
ULRICH FUCHS  and
KLAUS KRIEGEL
HELMUT ALT
Affiliation:
Institut für Informatik, Freie Universität Berlin, Takustr. 9, D-14195 Berlin, Germany (e-mail: alt@inf.fu-berlin.de kriegel@inf.fu-berlin.de) http://www.inf.fu-berlin.de/inst/ag-ti
KLAUS KRIEGEL
Affiliation:
Institut für Informatik, Freie Universität Berlin, Takustr. 9, D-14195 Berlin, Germany (e-mail: alt@inf.fu-berlin.de kriegel@inf.fu-berlin.de) http://www.inf.fu-berlin.de/inst/ag-ti
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.28n cycles. Applying some probabilistic arguments we prove an upper bound of 3.37n.

We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colourable triangulated graphs.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 8 , Issue 5 , September 1999 , pp. 397 - 405
Copyright
1999 Cambridge University Press