# 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].

In [1]:
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$.

In [2]:
base_graph,covering_graph,V,E= Graff(make_graph(),K)


The base graph $\Gamma$ is:

In [3]:
base_graph.graphplot(edge_labels=True,layout='spring').show()


The coverin graph $\tilde \Gamma$ is:

In [4]:
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:

In [5]:
pretty_print(Arborescence_ratio(1))


#### 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).