On the number of maximum genus embeddings of almost all graphs

DOI10.1016/0195-6698(92)90043-YMaRDI QIDQ1193548zbMATH OpenFDO

Authors Saul Stahl

Publication date 27 September 1992

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0195-6698(92)90043-Y

zbMATH Keywords

maximum genus embeddingsminimum genus imbeddings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

By performing an induction in the context of permutation-partition pairs, the author obtains a lower bound for the number of orientable maximum genus labelled 2-cell imbeddings of almost all graphs. He shows that, although the bound is far from sharp, it is sufficiently strong to establish that for complete graphs triangulating an orientable surface the number of maximum genus imbeddings far exceeds the number of minimum genus imbeddings.

Recommendations

• Maximum genus embeddings and genus embeddings on orientable surfaces
• Exponentially many maximum genus embeddings and genus embeddings for complete graphs
• Lower bound on the number of the maximum genus embedding of \(K_{n,n}\)
• Maximum genus and minimum genus embedding in non-orientable surfaces
• Lower bound of the number of maximum genus embeddings and genus embeddings of \(K_{12s+7}\)

Cites work

• A Characterization in of Upper-Embeddable Graphs
• An upper bound for the average number of regions
• Enumerating 2-Cell Imbeddings of Connected Graphs
• Genus distributions for bouquets of circles
• Genus distributions for two classes of graphs
• Hierarchy for imbedding-distribution invariants of a graph
• How to determine the maximum genus of a graph
• scientific article; zbMATH DE number 3843773 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 4095487 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• Permutation-Partition Pairs II: Bounds on the Genus of the Amalgamation of Graphs
• Permutation-partition pairs. III: Embedding distributions of linear families of graphs
• Permutation-Partition Pairs: A Combinatorial Generalization of Graph Embeddings
• Region distributions of graph embeddings and Stirling numbers
• Region distributions of some small diameter graphs
• Survey of results on the maximum genus of a graph
• The embeddings of a graph—A survey
• The nonorientable genus is additive
• The orientable genus is nonadditive

Cited in

(12)

• The maximum genus of graphs with diameter three
• Maximum genus of strong embeddings
• Maximum genus embeddings of Steiner triple systems
• Maximum genus of a graph in terms of its embedding properties.
• A tight lower bound on the maximum genus of a simplicial graph
• Exponentially many genus embeddings of the complete graph \(K_{12s+3}\)
• Enumerating the orientable 2-cell imbeddings of complete bipartite graphs
• Genus g Graphs Have Pagenumber O(√g)
• MAXIMUM GENUS EMBEDDINGS OF LATIN SQUARES
• Maximum genus embeddings and genus embeddings on orientable surfaces
• Lower bound of the number of maximum genus embeddings and genus embeddings of \(K_{12s+7}\)
• Number of embeddings of circular and Möbius ladders on surfaces

This page was built for publication: On the number of maximum genus embeddings of almost all graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1193548)