3-connected reduction for regular graph covers. (October 2018) - Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
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 Γ of Aut ( G ) ; so H ≅ G ∕ Γ . In this paper, we study the behavior of regular graph covering with respect to 1-cuts and2-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), Hopcroft 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 covering projections G i → H i where H i is the i th 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).