Tutte cycles in circuit graphs
type: Item
instance of: scholarly article
title: Tutte cycles in circuit graphs
zbMATH Open document ID: 0893.05008
DOI: 10.1016/S0012-365X(97)00154-4
author: Xingxing Yu
author: Zhicheng Gao
published in: Discrete Mathematics
publication date: 1998-08-11T00:00:00Z
review text: A Tutte cycle in a graph \(G\) is a cycle \(C\) such that each component \(H\) of \(G-C\) has at most three attachments on \(C\), i.e. at most three vertices of \(C\) have neighbours in \(H\). In the present paper, the authors prove that each 3-connected planar graph \(G\) contains a Tutte cycle \(C\) such that each component of \(G-C\) has less than \(| V(G) |/3\) vertices. This improves a former result of B. Jackson and N. C. Wormald who obtained the upper bound \(| V(G) |/2\). Such kinds of results are useful for obtaining lower bounds for the length of longest cycles in 3-connected planar graphs.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1121489
zbMATH Keywords: circuit graphs
zbMATH Keywords: Tutte cycle
zbMATH Keywords: planar graph
zbMATH Keywords: longest cycles
reviewed by: Andreas Huck
MaRDI profile type: Publication
cites work: Convex programming and circumference of 3-connected graphs of low genus
cites work: Longest cycles in 3-connected planar graphs
cites work: Simple paths on polyhedra
cites work: A theorem on paths in planar graphs
cites work: 4-connected projective planar graphs are Hamiltonian
cites work: A Theorem on Planar Graphs
full work available at URL: s0012-365x(97)00154-4
OpenAlex ID: W2069798056
Recommended article: Tutte paths and long cycles in circuit graphs
Recommended article: On circuits in graphs
Recommended article: Cycles in circuit graphs of matroids
Recommended article: Circuits in graphs embedded on the torus
Recommended article: Cycle lengths and circuit matroids of graphs
Recommended article: Cycle-connected graphs
Recommended article: Q3322124
Recommended article: Q4726282
description: scientific article; zbMATH DE number 1121489