Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649286 | Discrete Mathematics | 2010 | 5 Pages |
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
Xiaoyun Lu,