Long cycles in 3-connected graphs
type: Item
instance of: scholarly article
title: Long cycles in 3-connected graphs
zbMATH Open document ID: 1025.05036
author: Xingxing Yu
author: Guantao Chen
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: Let \(\text{circ}(G)\) denote the the length of the longest cycle in a graph \(G\). \textit{J. W. Moon} and \textit{L. Moser} [Pac. J. Math. 13, 629-631 (1963; Zbl 0115.41001)] exhibited a 3-connected planar graph \(G\) with \(n\) vertices for which \(\text{circ}(G)\leq 9n^{\log_32}\). The present authors show that if \(G\) is a 3-connected graph with \(n\) vertices that is embeddable in the sphere, the projective plane, the torus, or the Klein bottle, then \(\text{circ}(G)\geq \Omega(n^{\log_32})\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1843844
zbMATH Keywords: cycles
zbMATH Keywords: 3-connected graphs
reviewed by: J. W. Moon
MaRDI profile type: Publication
OpenAlex ID: W1988962142
cites work: Trees in Polyhedral Graphs
cites work: Spanning planar subgraphs of graphs in the torus and Klein bottle
cites work: Q3758863
cites work: Computing the orientable genus of projective graphs
cites work: Convex programming and circumference of 3-connected graphs of low genus
cites work: Shortness exponents of families of graphs
cites work: The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
cites work: Longest cycles in 3-connected planar graphs
cites work: Simple paths on polyhedra
cites work: A Theorem on Planar Graphs
Wikidata QID: Q56603446
DOI: 10.1006/JCTB.2002.2113
DBLP publication ID: journals/jct/ChenY02
Recommended article: Long cycles in 3-cyclable graphs
Recommended article: Longest cycles in 3-connected graphs
Recommended article: Q4294581
Recommended article: Q3360209
Recommended article: Long cycles passing through a specified edge in 3-connected graphs
Recommended article: Q3758863
Recommended article: Longest cycles in 3-connected planar graphs
Recommended article: Q3684149
Recommended article: Q3122902
description: scientific article; zbMATH DE number 1843844