3-connected reduction for regular graph covers. (October 2018)

• Record Type: Journal Article
• Authors: Fiala, Jiří; Klavík, Pavel; Kratochvíl, Jan; Nedela, Roman
• Is Part Of: European journal of combinatorics. Volume 73(2018)
• Page Start: 170
• Page End: 210
• Publication Date: 2018-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.06.002
• Languages: English
• ISSNs: 0195-6698

Abstract

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).