A tight lower bound on the maximum genus of a simplicial graph

DOI10.1016/0012-365X(95)00070-DzbMath0858.05041MaRDI QIDQ1923508

Jonathan L. Gross, Saroja P. Kanchi, Jian'er Chen

Publication date: 5 January 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

maximum genusminimum valencecycle ranksimplicial graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (16)

On the average crosscap number. II: Bounds for a graph ⋮ Maximum genus and connectivity ⋮ Algorithmic graph embeddings ⋮ New bounds for the average genus and average number of faces of a simple graph ⋮ Maximum genus and chromatic number of graphs ⋮ Remarks on the lower bounds for the average genus ⋮ On the lower bounds for the maximum genus for simple graphs ⋮ The maximum genus of a 3-regular simplicial graph ⋮ Maximum genus, girth and connectivity ⋮ The maximum genus of graphs with diameter three ⋮ Maximum genus and girth of graphs ⋮ Maximum genus, connectivity and minimal degree of graphs ⋮ A note on the maximum genus of 3-edge-connected nonsimple graphs ⋮ Lower bounds on the maximum genus of loopless multigraphs ⋮ A tight lower bound on the maximum genus of a 3-connected loopless multigraph ⋮ A tight lower bound on the maximum genus of \(3\)-edge connected loopless graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Region distributions of some small diameter graphs
• Region distributions of graph embeddings and Stirling numbers
• Limit points for average genus. I: 3-connected and 2-connected simplicial graphs
• On the number of maximum genus embeddings of almost all graphs
• Limit points for average genus. II: 2-connected non-simplicial graphs
• Kuratowski-type theorems for average genus
• An additivity theorem for maximum genus of a graph
• How to determine the maximum genus of a graph
• Upper-embeddable graphs and related topics
• Bounds of the number of disjoint spanning trees
• The maximum genus of graphs of diameter two
• On the average genus of a graph
• On the maximum genus of a graph
• A Kuratowski-type theorem for the maximum genus of a graph
• Hierarchy for imbedding-distribution invariants of a graph
• Every connected, locally connected graph is upper embeddable
• The Maximum Genus of Cartesian Products of Graphs
• A Characterization in of Upper-Embeddable Graphs
• Survey of results on the maximum genus of a graph
• Lower bounds for the average genus
• On the complexity of graph embeddings
• Determining all compact orientable 2-manifolds upon which \(K_{m,n}\) has 2-cell imbeddings

This page was built for publication: A tight lower bound on the maximum genus of a simplicial graph