Arborescence of Covering Graphs

Let $\Gamma$ be a directed graph with certain permutation volage assignment [1], and $\tilde \Gamma$ be its derived $K$-fold covering graph. This code compute $\tilde \Gamma$ and the ratio of arborescence ${A_{\tilde v}(\tilde \Gamma)}/{A_v(\Gamma)}$ [2].

K=3 
#This will be a K-fold cover

def make_graph(perm=None):
    if perm != None:
    # Use this if you want to range over different voltage assignments
        return [
   #((vertex,vertex,edge weight),permutation voltage)
    ((1,2,'a'),perm[0]),
    ((2,1,'b'),perm[1]),
    ((3,1,'d'),perm[2]),
    ((2,3,'c'),perm[3]),
    ((3,3,'e'),perm[4]),            
]
    else:
    # Otherwise make your own graph here.
        return [
       #((vertex,vertex,edge weight),permutation voltage)
        ((1,2,'a'),[0,1,2]),
        ((2,1,'b'),[1,2,0]),
        ((3,1,'d'),[1,0,2]),
        ((2,3,'c'),[0,2,1]),
        ((3,3,'e'),[1,2,0]),
    ]

def Graff(Input,K):
    Graff={}
    Graph=[]
    NoV=0
    NoE=0
    for A,P in Input:
        w=var(A[2])
        X=(A[0],A[1],w)
        Graff[X]=P
        Graph+=[X]
        for i in [A[0],A[1]]:
            if i>= NoV:
                NoV=i
    mygraff=DiGraph(Graph,loops=True,multiedges=True)
    CGraff=[]
    for i in range(K):
        for e,p in Graff.items():
            a=e[0]+NoV*i
            b=e[1]+NoV*p[i]
            c=e[2]
            CGraff+=[(a,b,c)]
    mycovergraff=DiGraph(CGraff,loops=True,multiedges=True)
    return mygraff,mycovergraff,NoV,NoE


def Arborescence(graff,i):
    #The Arborescence of a graph rooted at vertex i
    v=len(graff.vertices())
    List=[]
    k=0
    for q in range(v):
        if k != i-1:
            List+=[k]
        k+=1
    L=graff.kirchhoff_matrix(indegree=False,weighted=True)
    A=L.matrix_from_rows_and_columns(List,List)
    return det(A).expand()

def Arborescence_ratio(i,Input=make_graph()):
    myg,mycg,nov,noe=Graff(Input,K)
    Arb=Arborescence(mycg,i)
    arb=Arborescence(myg,i)
    ratio=(Arb/arb).full_simplify().expand()
    return ratio

Now creating the coveing graph: Let $v$ be the number of vertices, then the vertex $i$ will be lifted to $i,i+n,i+2n,\cdots,i+Kv$.

base_graph,covering_graph,V,E= Graff(make_graph(),K)

The base graph $\Gamma$ is:

base_graph.graphplot(edge_labels=True,layout='spring').show()

The coverin graph $\tilde \Gamma$ is:

covering_graph.graphplot(edge_labels=True,layout='spring').show()

The ratio of arborescence of the covering graph $\tilde \Gamma$ over the arborescence of $\Gamma$ is:

pretty_print(Arborescence_ratio(1))

$$\newcommand{\Bold}[1]{\mathbf{#1}}a^{2} b^{2} d^{2} + 2 \, a^{2} b c d^{2} + a^{2} c^{2} d^{2} + 3 \, a^{2} b^{2} d e + 4 \, a^{2} b c d e + a^{2} c^{2} d e + 3 \, a^{2} b^{2} e^{2} + 3 \, a^{2} b c e^{2} + a^{2} c^{2} e^{2}$$

References

[1] Gross, Jonathan L., and Thomas W. Tucker. "Generating all graph coverings by permutation voltage assignments." Discrete Mathematics 18, no. 3 (1977): 273-283.

[2] Chepuri, Sunita, C. J. Dowd, Andy Hardt, Gregory Michel, Sylvester W. Zhang, and Valerie Zhang. "Arborescences of Covering Graphs." arXiv preprint arXiv:1912.01060 (2019).