A common cover of graphs and 2-cell embeddings (Q1057277)

A partition \(V_ 1\cup V_ 2\cup...\cup V_ n\) of the vertex set of a graph G is a degree partition if there are numbers \(r_{ij}\), \(1\leq i\), \(j\leq n\), such that for each j and each \(v\in V_ i\) there are exactly \(r_{ij}\) edges from v to vertices in \(V_ j\). The corresponding \(n\times n\) matrix \(R=(r_{ij})\) is called a degree refinement which is said to be uniform if in each row of R all nonzero numbers are pairwise equal. Let G and H be finite graphs with equal uniform degree refinements. Then their common covering graph \(G\circ H\) is constructed. It is shown that G, H and \(G\circ H\) can be 2-cell embedded in orientable surfaces M, N and S, respectively, in such a way that the graph covering projections \(G\circ H\to G\) and \(G\circ H\to H\) extend to branched coverings \(M\leftarrow S\to\) of the surfaces. Additional properties of \(G\circ H\) are used to obtain some nontrivial consequences about coverings of some planar graphs, generalizing some results of Fisk, Gallai, Kotzig, Malkevitch and Motzkin.