Genus distributions for two classes of graphs
type: Item
instance of: scholarly article
title: Genus distributions for two classes of graphs
zbMATH Open document ID: 0669.05028
DOI: 10.1016/0095-8956(89)90004-X
author: Merrick Furst
author: Jonathan L. Gross
author: Richard Statman
published in: Journal of Combinatorial Theory. Series B
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 4095488
zbMATH Keywords: genus distribution
zbMATH Keywords: embeddings of a graph
zbMATH Keywords: 3-regular closedend ladders
zbMATH Keywords: 4-regular cobblestone paths
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
cites work: The topological theory of current graphs
cites work: Hierarchy for imbedding-distribution invariants of a graph
cites work: Q3757929
cites work: Orientable embedding of Cayley graphs
cites work: Some Results for Discrete Unimodality
cites work: Q5581642
cites work: Q4773723
cites work: SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
cites work: Q3866122
cites work: Q3344220
cites work: Q3847965
full work available at URL: 0095-8956(89)90004-x
OpenAlex ID: W2092657801
description: scientific article; zbMATH DE number 4095488