A tight lower bound on the maximum genus of a simplicial graph
type: Item
instance of: scholarly article
title: A tight lower bound on the maximum genus of a simplicial graph
zbMATH Open document ID: 0858.05041
DOI: 10.1016/0012-365X(95)00070-D
author: Saroja P. Kanchi
author: Jonathan L. Gross
author: Jianer Chen
published in: Discrete Mathematics
publication date: 1997-01-05T00:00:00Z
review text: Every connected simplicial graph has maximum genus at most one-half of its cycle rank [\textit{E. A. Nordhaus}, \textit{B. M. Stewart}, and the reviewer, J. Comb. Theory, Ser. B 11, 258-267 (1971; Zbl 0217.02204)]. In the present paper it is shown that such graphs having minimum valence at least three have maximum genus more than one-quarter of their cycle rank, and that this lower bound is tight. Examples of necklace multigraphs are given to show that both the simplicial and the minimum valence assumptions are essential. Applications are given to the average genus of simplicial graphs for which all vertices have valence at least three: average genus exceeds one-eighth of the cycle rank, and hence one-quarter of the maximum genus.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 932551
zbMATH Keywords: maximum genus
zbMATH Keywords: cycle rank
zbMATH Keywords: minimum valence
zbMATH Keywords: simplicial graphs
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Q4281636
cites work: Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
cites work: Limit points for average genus. II: 2-connected non-simplicial graphs
cites work: Kuratowski-type theorems for average genus
cites work: Lower bounds for the average genus
cites work: On the complexity of graph embeddings
cites work: Hierarchy for imbedding-distribution invariants of a graph
cites work: On the average genus of a graph
cites work: Q3757929
cites work: Q4147999
cites work: A Characterization in of Upper-Embeddable Graphs
cites work: Bounds of the number of disjoint spanning trees
cites work: Every connected, locally connected graph is upper embeddable
cites work: A Kuratowski-type theorem for the maximum genus of a graph
cites work: On the maximum genus of a graph
cites work: Q4073393
cites work: An additivity theorem for maximum genus of a graph
cites work: Determining all compact orientable 2-manifolds upon which \(K_{m,n}\) has 2-cell imbeddings
cites work: Survey of results on the maximum genus of a graph
cites work: The maximum genus of graphs of diameter two
cites work: Region distributions of graph embeddings and Stirling numbers
cites work: Region distributions of some small diameter graphs
cites work: On the number of maximum genus embeddings of almost all graphs
cites work: Q4156452
cites work: How to determine the maximum genus of a graph
cites work: Upper-embeddable graphs and related topics
cites work: The Maximum Genus of Cartesian Products of Graphs
description: scientific article; zbMATH DE number 932551