On the number of cycles of length <i>k</i> in a maximal planar graph

Abstract

Abstract Let G be a maximal planar graph with p vertices, and let C k ( G ) denote the number of cycles of length k in G . We first present tight bounds for C 3 ( G ) and C 4 ( G ) in terms of p . We then give bounds for C k ( G ) when 5 ≤ k ≤ p, and consider in particular bounds for C p ( G ), in terms of p . Some conjectures and unsolved problems are stated.