Bounds for the average genus of the vertex-amalgamation of graphs

✍ Scribed by Saul Stahl

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 628 KB
• Volume: 142
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)e0221-o

✦ Synopsis

The average orientable genus of graphs has been the subject of a considerable number of recent investigations. It is the purpose of this article to examine the extent to which the average genus of the amalgamation of graphs fails to be additive over its constituent subgraphs. This discrepancy is bounded and the sharpness of these bounds discussed and compared to similar bounds for the minimum and the maximum genera of the amalgamation of graphs. The main result relies on permutation-partition pairs for its proof.

1. Background

A graph G is permitted to have both loops and multiple edges. If we view G as a one-dimensional CW complex, then an embedding of G is a homeomorphism of G into some closed oriented surface S such that the complement of the image of G in S consists of the disjoint union of open 2-cells. Since the surface is oriented, every such embedding induces at each vertex v of G a cyclic orientation R, of the directed edges of G that emanate from v. The set R = (R,) v E V(G)} is called a rotation system of G and two embeddings of G are considered to be equivalent if they define identical rotation systems of G. It follows that every graph G has the following finite number of embeddings: oel-j,, Cdedv) -II!.

Initially, topological graph theorists focused their attention on the minimum genus of all the embeddings of G. Later, attention