Genus distributions for two classes of graphs (Q1118607)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Genus distributions for two classes of graphs |
scientific article |
Statements
Genus distributions for two classes of graphs (English)
0 references
1989
0 references
The minimum genus (maximum genus) of a graph is defined as the minimum h (maximum h respectively) such that the graph embeds in the sphere with h handles. Duke's interpolation theorem implies that the graph embeds on every surface lying between this minimum and maximum. The authors study how the embeddings of a graph are distributed among these surfaces for two infinite classes of graphs. The first class is the 3-regular closedend ladders, defined as \(P_ n\times K_ 2\) where the edges joining the ends of the paths are duplicated. The second class is the 4- regular cobblestone paths, constructed from \(P_ n\) by duplicating each edge and adding a loop on each end. The authors give formulas for the number of embeddings of these graphs into each surface. These are the first (nontrivial) classes of graphs for which these calculations have be done.
0 references
genus distribution
0 references
embeddings of a graph
0 references
3-regular closedend ladders
0 references
4-regular cobblestone paths
0 references