Cycle lengths in planar graphs

Abstract

Let C(G) denote the set of lengths of cycles in a graph G, and let CP(n) denote the number of distinct subsets C(G) ⊂ {1,2,..., n} where G is a hamiltonian planar graph on n vertices. In this paper, we prove that CP(n) ≤ 2^cn, where c < 1 is an absolute positive constant. This compares with the constructive lower bound CP(n) ≥ 2^n/2 given by Faudree.