A note on 3-connected cubic planar graphs

被引：4

作者：

Lu, Xiaoyun ^{[1
]}

机构：

[1] US Bur Census, Amer Community Survey Off, Suitland, MD USA

来源：

DISCRETE MATHEMATICS | 2010年 / 310卷 / 13-14期

关键词：

Longest cycle; 3-connected cubic planar graph; Hamilton cycle; Hamiltonian; Non-hamiltonian; Tutte fragment;

D O I：

10.1016/j.disc.2010.03.010

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 - root n + 49/4 + 5/2 holds for infinitely many integers n. The exact value of c(n) is unknown. Published by Elsevier B.V.

引用

页码：2054 / 2058

页数：5

共 8 条

[1] Bondy J.A., 2008, GTM
[2] Long cycles in 3-connected graphs
Chen, GT
Yu, XX
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (01) : 80 - 99
[3] THE SMALLEST NON-HAMILTONIAN 3-CONNECTED CUBIC PLANAR GRAPHS HAVE 38 VERTICES
HOLTON, DA
MCKAY, BD
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1988, 45 (03) : 305 - 319
[4] SIMPLE PATHS ON POLYHEDRA
MOON, JW
MOSER, L
[J]. PACIFIC JOURNAL OF MATHEMATICS, 1963, 13 (02) : 629 - &
[5] Tait P., 1884, Philos. Mag, V17, P30
[6] Tutte W.T., 1946, J. Lond. Math. Soc., V21, P98, DOI 10.1112/jlms/s1-21.2.98
[7] Tutte W. T., 1956, Trans. Amer. Math. Soc., V82, P99, DOI DOI 10.1090/S0002-9947-1956-0081471-8
[8] TUTTE WT, 1998, OXFORD LECT SERIES M

← 1 →