Citation
Zc. Gao et Xx. Yu, CONVEX-PROGRAMMING AND CIRCUMFERENCE OF 3-CONNECTED GRAPHS OF LOW GENUS, J COMB TH B, 69(1), 1997, pp. 39-51
Citations number
14
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
69
Issue
1
Year of publication
1997
Pages
39 - 51
Database
ISI
SICI code
0095-8956(1997)69:1<39:CACO3G>2.0.ZU;2-T
Abstract
The circumference of a graph G is the length of a longest cycle in G.
In this paper, we shall show that, if G is a 3-connected graph embedda
ble in the plane, the projective plane, the torus, or the Klein bottle
, then G has circumference at least (1/6) x \V(G)\(0.4) + 1. This impr
oves a result of Jackson and Wormald. (C) 1997 Academic Press.