Enumeration of Graph Coverings and Their Generalization

点击翻译按钮获取中文摘要

We consider four objects in enumeration of graph coverings and their generalization : enumeration of regular coverings ; enumeration of g-cyclic A-covers ; lifts of automorphisms of symmetric digraphs; zeta functions of regular coverings.The general problem of counting the ismorphism classes of regular n-fold coverings of a graph G with respect to a group Γ of automorphisms of G is still unsolved except in the case that n is prime. The enumeration of Γ-isomorphism classes of regular p^n-fold coverings of G is a natural problem. A regular p^2-fold covering of G is either a Z_p×Z_p-covering or a Z_<p2>-covering of G. We enumerate the Γ-isomorphism classes of Z_p×Z_p-coverings of G.Furthermore, we show that it is possible to count the Γ-isomorphism classes of Z_p^n-coverings of G for any prime p(>2) and any 3≦n≦p.Next, for a connected symmetric digraph D, a finite group A and g∈A, we consider a g-cyclic A-cover of D as a generalization of a regular covering of a graph. We enumerate the Γ-isomorphism classes of g-cyclic Z_p×Z_p-covers and g-cyclic Z_p^3-covers of D. In the case that A is an abelian group, we present a characterization for two g-cyclic A-covers of D to be ismorphic with respect to a group Γ of automorphisms of D. Thus, we enumerate the I-isomorphism classes of g-cyclic Z_2^n-covers and g-cyclic Z_<2n>-covers of D.For a group Γ of automorphisms of a symmetric digraph D, we present a necessary and sufficient condition for Γ to have a lift with respect to a cyclic A-cover of D, and characterize the lift of Γ to be a split extension of A by Γ.As an application of a decomposition formula for the characteristic polynomial of a regular covering of a graph G, we obtain a factorization of the zeta function of a regular covering of G. Furthermore, we factorize the zeta function of a g-cyclic A-cover of a symmetric digraph.