Maximum genus and connectivity
type: Item
instance of: scholarly article
title: Maximum genus and connectivity
zbMATH Open document ID: 0843.05019
DOI: 10.1016/0012-365X(94)00336-H
author: Jonathan L. Gross
author: Jianer Chen
author: Dan S. Archdeacon
published in: Discrete Mathematics
publication date: 1996-03-25T00:00:00Z
review text: The authors show that the tight lower bound for the maximum genus of a 2-edge-connected simplicial graph is \(\lceil \beta(G)/3\rceil\), where \(\beta(G)\) is the cycle rank of graph \(G\). This compares with the well-known tight upper bound \(\lfloor \beta(G)/2\rfloor\), for arbitrary connected graphs \(G\). They develop a general method for constructing 3-vertex-connected graphs which attain the lower bound above; in combination with results of Chen, Kanchi, and Gross (Discrete Math., to appear) and of Kanchi and Chen (Manuscript, 1992), the new results give a complete picture of the tight lower bounds for the maximum genus of simplicial graphs. \textit{S. Kundu} [J. Comb. Theory, Ser. B 17, 199-203 (1974; Zbl 0285.05113)] and \textit{N. H. Zuong} [J. Comb. Theory, Ser. B 26, 217-225 (1979; Zbl 0403.05035)] showed that the upper bound above is attained, for all 4-vertex-connected (or 4-edge-connected) graphs.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 858098
zbMATH Keywords: connectivity
zbMATH Keywords: bound
zbMATH Keywords: maximum genus
zbMATH Keywords: simplicial graph
zbMATH Keywords: cycle rank
zbMATH Keywords: connected graphs
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q4200065
cites work: Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
cites work: Kuratowski-type theorems for average genus
cites work: A tight lower bound on the maximum genus of a simplicial graph
cites work: Hierarchy for imbedding-distribution invariants of a graph
cites work: On the average genus of a graph
cites work: Q3757929
cites work: A Characterization in of Upper-Embeddable Graphs
cites work: Bounds of the number of disjoint spanning trees
cites work: A new characterization of the maximum genus of a graph
cites work: Sur un Theoreme Min-Max En Theorie Des Graphes (D'Après L. Nebeský)
cites work: Q3216652
cites work: Q4156452
cites work: How to determine the maximum genus of a graph
description: scientific article; zbMATH DE number 858098