On the Circumference of 3-Connected Cubic Triangle-Free Plane Graphs

The circumference of a graph G is the length of a longest cycle in G , denoted by cir G . For any even number n , let c n  = min { cir G | G is a 3-connected cubic triangle-free plane graph with n vertices}. In this paper, we show that an upper bound of c n is n + 1 − 3 ⌊ n / 136 ⌋ for n ≥ 136 .