Abstract
A graph G covers a graph H if there exists a locally bijective homomorphism from G to H. We deal with regular coverings in which this homomorphism is prescribed by an action of a semiregular subgroup Gamma of Aut(G): so H congruent to G/Gamma.
In this paper, we study the behavior of regular graph covering with respect to 1-cuts and 2-cuts in G. We describe reductions which produce a series of graphs G = G(0), . . . , G(r) such that G(i+1) is created from G(i) by replacing certain inclusion minimal subgraphs with colored edges.
The process ends with a primitive graph G(r) which is either 3-connected, or a cycle, or K-2. This reduction can be viewed as a non-trivial modification of reductions of Mac Lane (1937), Trachtenbrot (1958), Tutte (1966), Hoperoft and Tarjan (1973), Cuningham and Edmonds (1980), Walsh (1982), and others.
A novel feature of our approach is that in each step all essential information about symmetries of G are preserved. A regular covering projection G(0) -> H-0 induces regular cover- ing projections G(i) -> H-i where H-i is the ith quotient reduction of H-0.
This property allows to construct all possible quotients H-0 of G(0) from the possible quotients H-r of G(r). By applying this method to planar graphs, we give a proof of Negami's Theorem (1988).
Our structural results are also used in subsequent papers for regular covering testing when G is a planar graph and for an inductive characterization of the automorphism groups of planar graphs (see Babai (1973) as well). (C) 2018 Elsevier Ltd. All rights reserved.