On the maximum number of cycles in a planar graph |
| |
| Authors: | R E L Aldred Carsten Thomassen |
| |
| Institution: | 1. Department of Mathematics and Statistics, University of Otago P. O. Box 56, Dunedin, New Zealand;2. Department of Mathematics, Technical University of Denmark DK‐2800 Lyngby, Denmark |
| |
| Abstract: | Let G be a graph on p vertices with q edges and let r = q ? p = 1. We show that G has at most  cycles. We also show that if G is planar, then G has at most 2r ? 1 = o(2r ? 1) cycles. The planar result is best possible in the sense that any prism, that is, the Cartesian product of a cycle and a path with one edge, has more than 2r ? 1 cycles. © Wiley Periodicals, Inc. J. Graph Theory 57: 255–264, 2008 |
| |
| Keywords: | graphs maximum number of cycles |
|
|
