Genus distributions for two classes of graphs (Q1118607)

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.