Article ID Journal Published Year Pages File Type
4649286 Discrete Mathematics 2010 5 Pages PDF
Abstract

The length of a longest cycle in a graph GG is called the circumference   of GG and is denoted by c(G)c(G). Let c(n)=min{c(G):G is a 3-connected cubic planar graph of order n}c(n)=min{c(G):G is a 3-connected cubic planar graph of order n}. Tait conjectured in 1884 that c(n)=nc(n)=n, and Tutte disproved this in 1946 by showing that c(n)≤n−1c(n)≤n−1 for n=46n=46. We prove that the inequality c(n)≤n−n+494+52 holds for infinitely many integers nn. The exact value of c(n)c(n) is unknown.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,