# 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

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