Enumeration of graph embeddings
type: Item
instance of: scholarly article
title: Enumeration of graph embeddings
zbMATH Open document ID: 0813.05034
DOI: 10.1016/0012-365X(93)E0075-F
author: Jaeun Lee
author: Jin Ho Kwak
published in: Discrete Mathematics
publication date: 1995-02-01T00:00:00Z
review text: Let \(G\) be a finite connected simple graph, with \(\Gamma\) a subgroup of \(\Aut G\). Two 2-cell imbeddings \(i: G\to S\) and \(j: G\to S\) of \(G\) into a closed surface \(S\) (orientable or nonorientable) are said to be congruent with respect to \(\Gamma\) if there exist a surface homeomorphism \(h: S\to S\) and a \(\gamma\in \Gamma\) such that \(h\circ i= j\circ \gamma\). The authors give an algebraic characterization of congruent 2-cell imbeddings (with respect to \(\Gamma\)). This is used to enumerate the corresponding congruence classes. This work substantially generalizes that of \textit{B. P. Mull}, \textit{R. G. Rieper} and the reviewer [Proc. Am. Math. Soc. 103, No. 1, 321-330 (1988; Zbl 0653.05028)], which deals with the oriented congruence of imbeddings of a fixed graph into orientable surfaces, with respect to \(\Gamma= \Aut G\).
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 716453
zbMATH Keywords: enumeration
zbMATH Keywords: graph embeddings
zbMATH Keywords: 2-cell imbeddings
zbMATH Keywords: closed surface
zbMATH Keywords: surface homeomorphism
zbMATH Keywords: algebraic characterization
zbMATH Keywords: congruence
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Generalizing the duality theorem of graph embeddings
cites work: Q5422499
cites work: Overlap matrices and total imbedding distributions
cites work: Hierarchy for imbedding-distribution invariants of a graph
cites work: Genus distributions for bouquets of circles
cites work: Generating all graph coverings by permutation voltage assignments
cites work: Q3757929
cites work: Counting double covers of graphs
cites work: Isomorphism Classes of Graph Bundles
cites work: Counting some finite-fold coverings of a graph
cites work: Isomorphism classes of cycle permutation graphs
cites work: An obstruction to embedding graphs in surfaces
cites work: Enumerating 2-Cell Imbeddings of Connected Graphs
cites work: Uniqueness and faithfulness of embedding of toroidal graphs
cites work: Enumeration of projective-planar embeddings of graphs
cites work: Generalized Embedding Schemes
cites work: The embeddings of a graph—A survey
full work available at URL: 0012-365x(93)e0075-f
OpenAlex ID: W1996053377
Recommended article: Enumeration of digraph embeddings
Recommended article: Q4002103
Recommended article: Embeddings of graphs
Recommended article: Enumerating Unlabelled Embeddings of Digraphs
Recommended article: Q3491600
Recommended article: Q2949150
Recommended article: Q3720609
Recommended article: Enumeration of projective-planar embeddings of graphs
Recommended article: Enumerating graph embeddings and partial-duals by genus and Euler genus
Recommended article: Q4716822
description: scientific article; zbMATH DE number 716453