UP - logo
Univerza na Primorskem Univerzitetna knjižnica - vsi oddelki (UPUK)
PDF
  • Some computational aspects of solvable regular covers of graphs
    Požar, Rok, 1986-
    Given a connected graph ▫$X$▫ and a group ▫$G$▫ of its automorphisms we first introduce an approach for constructing all pairwise nonequivalent connected solvable regular coverings ▫$\wp \colon ... \widetilde{X} \to X$▫ (that is, with a solvable group of covering transformations CT▫$(\wp)$▫) along which ▫$G$▫ lifts, up to a prescribed order ▫$n$▫ of ▫$\widetilde{X}$▫. Next, given a connected solvable regular covering ▫$\wp \colon \widetilde{X} \to X$▫ by means of voltages and a group ▫$G \le \text{Aut}(X)$▫ that lifts along ▫$\wp$▫, we consider algorithms for testing whether the lifted group ▫$\widetilde{X}$▫ is a split extension of CT▫$(\wp)$▫. In computational group theory, methods for testing whether a given extension of permutation groups splits are known. However, in order to apply the existing algorithms, ▫$\widetilde{X}$▫ together with CT▫$(\wp)$▫ and ▫$\widetilde{G}$▫ need to be constructed in the first place, which is far from optimal. Recently, an algorithm avoiding such explicit constructions has been proposed by Malnič and Požar (On the Split Structure of Lifted Groups, submitted for publication). We here provide additional details about this algorithm and investigate its performance compared to the one using explicit constructions. To this end, a concrete dataset of solvable regular covers of graphs has been generated by the algorithm mentioned in the first paragraph.
    Vir: Journal of symbolic computation. - ISSN 0747-7171 (Vol. 70, 2015, str. 1-13)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 1536900548

    Povezava(-e):

    http://dx.doi.org/10.1016/j.jsc.2014.09.023
    DOI

Vnos na polico