zbMATH — the first resource for mathematics

The maximum genus of a graph and doubly Eulerian trails. (English) Zbl 0715.05018
The maximum genus \(\gamma_ M(G)\) of a connected graph G is the maximum among the genera of all closed orientable 2-manifolds in which G has a 2- cell imbedding. This paper presents a new combinatorial characterization of the maximum genus parameter. In particular, let E(G) denote the edge set of the connected graph G, with \(D(G)=\{(u,v)| \{u,v\}\in E(G)\}\). A doubly Eulerian trail in G is a cyclic permutation \(\epsilon\) of D(G) such that the terminal vertex of each \(\chi\in D(G)\) coincides with the initial vertex of \(\epsilon\) (x). Let \(\tau (x)=x^{-1}\), for each \(x\in D(G)\), and let \(\| \epsilon^*\|\) give the number of orbits of the permutation \(\epsilon\tau\). Finally, let \(\zeta (G)=\beta (G)-2\gamma_ M(G)\), where \(\beta (G)=| E(G)| -| V(G)| +1\). The main result of this paper is that \(\zeta (G)=\min \{\| \epsilon^*\| - | V(G)\|\epsilon\) is a doubly Eulerian trail in \(G\}\). Several interesting applications are given, such as: G Eulerian with most two vertices of degree \(\equiv 0\) (mod 4) is necessarily upper imbeddable \((\gamma_ M(G)=\lfloor \beta (G)/2\rfloor)\).
Reviewer: A.T.White

05C10 Planar graphs; geometric and topological aspects of graph theory