Back to Search
Start Over
A note on 3-connected cubic planar graphs
- Source :
- Discrete Mathematics. 310(13-14):2054-2058
- Publication Year :
- 2010
- Publisher :
- Elsevier BV, 2010.
-
Abstract
- The length of a longest cycle in a graph G is called the circumference of G and is denoted by c(G). Let c(n)=min{c(G):G is a 3-connected cubic planar graph of order n}. Tait conjectured in 1884 that c(n)=n, and Tutte disproved this in 1946 by showing that c(n)≤n−1 for n=46. We prove that the inequality c(n)≤n−n+494+52 holds for infinitely many integers n. The exact value of c(n) is unknown.
- Subjects :
- Discrete mathematics
3-connected cubic planar graph
Non-hamiltonian
Nowhere-zero flow
Hamiltonian
Planar graph
Theoretical Computer Science
Combinatorics
Tutte fragment
symbols.namesake
Graph power
Hamilton cycle
Wheel graph
symbols
Graph minor
Cubic graph
Tutte 12-cage
Discrete Mathematics and Combinatorics
Longest cycle
Polyhedral graph
Mathematics
Subjects
Details
- ISSN :
- 0012365X
- Volume :
- 310
- Issue :
- 13-14
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....c589c108f968ad2a3156be82924a8488
- Full Text :
- https://doi.org/10.1016/j.disc.2010.03.010