Convex programming and circumference of 3-connected graphs of low genus
type: Item
instance of: scholarly article
title: Convex programming and circumference of 3-connected graphs of low genus
zbMATH Open document ID: 0867.05041
author: Xingxing Yu
author: Zhicheng Gao
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-08-03T00:00:00Z
review text: The circumference of a graph \(G\) is the length of a longest cycle in \(G\). We show that, if \(G\) is a 3-connected graph embeddable in the plane, the projective plane, the torus, or the Klein bottle, then \(G\) has circumference at least \((1/6)\times|V(G)|^{0.4}+1\). This improves a result of \textit{B. Jackson} and \textit{N. C. Wormald} [J. Comb. Theory, Ser. B 54, No. 2, 291-321 (1992; Zbl 0696.05031)].
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1006484
zbMATH Keywords: Tutte path
zbMATH Keywords: circuit graph
zbMATH Keywords: connectivity
zbMATH Keywords: circumference
zbMATH Keywords: longest cycle
zbMATH Keywords: projective plane
zbMATH Keywords: torus
zbMATH Keywords: Klein bottle
MaRDI profile type: Publication
full work available at URL: jctb.1996.1719
OpenAlex ID: W2013837525
DOI: 10.1006/JCTB.1996.1719
description: scientific article; zbMATH DE number 1006484