Description
Covering techniques play an important role not only in mathematics, but also in other areas, especially in those dealing with representation and analysis of large structural objects. One of the key properties of graph coverings is that all the information about a (usually) large covering graph can be encoded combinatorially in terms of voltages assigned to directed edges of a (relatively) small base graph. Moreover, the study of structural properties of covering graphs often reduces to the study of voltage distribution on the base graph. Combinatorial techniques developed for this purpose are based on the concept of lifting automorphisms.
In the talk we present adequate algorithms for solving certain natural problems regarding lifting automorphisms along combinatorially given covering projection. Speaking of algorithmic and complexity issues one would certainly first need to address the question of how difficult is to test whether an automorphisms of the base graph lifts at all. We how that for this problem, we can develop an efficient algorithm. Further, we focus on algorithms for analysing the structure of lifted group long regular covering projection: an algorithm for testing whether the lifted group is a split extension, and algorithm for testing whether the lifted group is a sectional split extension are given. All algorithms avoid explicit constructions of the covering graph as well as of the lifted group, since such constructions are time and space consuming in general. Joint work with Aleksander Malnič.
Primary author
Dr
Rok Požar
(University of Primorska)
