3-connected reduction for regular graph covers

DOI10.1016/J.EJC.2018.06.002zbMATH Open1393.05207arXiv1503.06556OpenAlexW2964181120WikidataQ129490625 ScholiaQ129490625MaRDI QIDQ1663806FDOQ1663806

Jan Kratochvíl, Jiří Fiala, Roman Nedela, Pavel Klavík

Publication date: 24 August 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

G a m m a

of

e x t r m A u t (G)

; so

H c o n g G / G a m m a

. In this paper, we study the behaviour 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}, d o t s, 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} o H_{0}

induces regular covering projections

G_{i} o 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).

Full work available at URL: https://arxiv.org/abs/1503.06556

zbMATH Keywords

covering fold number spherical genus weak spherical genus weakly vitually planar graphs \(n\)-fold covering

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

Cited In (6)

This page was built for publication: 3-connected reduction for regular graph covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663806)