BDGLRSY18-Distance_Laplacian

1505 days ago by hogben

# This worksheet contains verifications used in the paper # Graphs that are cospectral for the distance Laplacian # by Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, and Mark Yarrow 
       
################################ # Definitions of Sage functions ################################ 
       
# Definition of Distance Laplacian def distLap(G): n=G.order() ones = ones_matrix(n,1) dg=G.distance_matrix() trg=dg*ones DL=diagonal_matrix(vector(trg))-dg return DL 
       
# Definition of transmission sequence def trs(G): n=G.order() ones = ones_matrix(n,1) dg=G.distance_matrix() trg=vector(dg*ones) trgs=trg.list() trgs.sort() return trgs 
       
# count # pairs each distance def dist(m): nr=m.nrows() dist = zero_vector(nr) dist[0]=nr for i in [0..nr-1]: for j in [i+1..nr-1]: d=-m[i,j] dist[d]=dist[d]+1 return dist 
       
################################ # Example 2.1: degree sequence and transmission sequence ################################ 
       
g=Graph('FoL^w') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('F@V~o') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
print g.degree_sequence() print h.degree_sequence() 
       
[6, 4, 4, 3, 3, 3, 3]
[5, 5, 4, 4, 3, 3, 2]
[6, 4, 4, 3, 3, 3, 3]
[5, 5, 4, 4, 3, 3, 2]
print trs(g) print trs(h) 
       
[6, 8, 8, 9, 9, 9, 9]
[7, 7, 8, 8, 9, 9, 10]
[6, 8, 8, 9, 9, 9, 9]
[7, 7, 8, 8, 9, 9, 10]
################################ # Example 2.2: number edges and girth and distance multiset ################################ 
       
g=Graph('HhCWMES') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('HhDGKUO') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?,
13.50478622306352?, 14.3727299204472?, 16.1088581941218?,
16.8817006711310?, 21.13192499123656?]
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?,
13.50478622306352?, 14.3727299204472?, 16.1088581941218?,
16.8817006711310?, 21.13192499123656?]
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 +
491069091*x^3 - 2237203064*x^2 + 4446151812*x
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 +
491069091*x^3 - 2237203064*x^2 + 4446151812*x
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?, 13.50478622306352?, 14.3727299204472?, 16.1088581941218?, 16.8817006711310?, 21.13192499123656?]
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?, 13.50478622306352?, 14.3727299204472?, 16.1088581941218?, 16.8817006711310?, 21.13192499123656?]
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 + 491069091*x^3 - 2237203064*x^2 + 4446151812*x
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 + 491069091*x^3 - 2237203064*x^2 + 4446151812*x
print g.num_edges() print h.num_edges() 
       
13
12
13
12
print g.girth() print h.girth() 
       
3
4
3
4
print dist(DL1) print dist(DL2) 
       
(9, 13, 17, 6, 0, 0, 0, 0, 0)
(9, 12, 19, 5, 0, 0, 0, 0, 0)
(9, 13, 17, 6, 0, 0, 0, 0, 0)
(9, 12, 19, 5, 0, 0, 0, 0, 0)
################################ # Figure 2.3: diameter ################################ 
       
g=Graph('IzRxzEHHg') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('I~{KHNgiG') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?,
16.41421356237310?, 11.763932022500211?, 11.763932022500211?,
16.23606797749979?, 16.23606797749979?]
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?,
16.41421356237310?, 11.763932022500211?, 11.763932022500211?,
16.23606797749979?, 16.23606797749979?]
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 +
797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 +
797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?, 16.41421356237310?, 11.763932022500211?, 11.763932022500211?, 16.23606797749979?, 16.23606797749979?]
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?, 16.41421356237310?, 11.763932022500211?, 11.763932022500211?, 16.23606797749979?, 16.23606797749979?]
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 + 797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 + 797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
print g.diameter() print h.diameter() 
       
3
2
3
2
################################ # Figure 2.4: leaf ################################ 
       
g=Graph('G@OZN{') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('G_C`~{') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[15, 14, 13, 10, 8, 0, 12, 12]
[15, 14, 13, 10, 8, 0, 12, 12]
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 +
19080000*x^2 - 31449600*x
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 +
19080000*x^2 - 31449600*x
[15, 14, 13, 10, 8, 0, 12, 12]
[15, 14, 13, 10, 8, 0, 12, 12]
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 + 19080000*x^2 - 31449600*x
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 + 19080000*x^2 - 31449600*x
print g.degree_sequence() print h.degree_sequence() 
       
[7, 4, 4, 3, 3, 3, 3, 1]
[7, 5, 3, 3, 3, 3, 2, 2]
[7, 4, 4, 3, 3, 3, 3, 1]
[7, 5, 3, 3, 3, 3, 2, 2]
################################ # Figure 2.5: dominating vertex ################################ 
       
g=Graph('FIefw') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('F@R~o') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[9, 7, 0, 12, 12, 10, 10]
[9, 7, 0, 12, 12, 10, 10]
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
[9, 7, 0, 12, 12, 10, 10]
[9, 7, 0, 12, 12, 10, 10]
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
print g.degree_sequence() print h.degree_sequence() 
       
[6, 3, 3, 3, 3, 3, 3]
[5, 5, 3, 3, 3, 3, 2]
[6, 3, 3, 3, 3, 3, 3]
[5, 5, 3, 3, 3, 3, 2]
################################ # Figure 2.6: cut-vertex ################################ 
       
g=Graph('G`Gx}{') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('GBXk{{') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 +
18666240*x^2 - 30643200*x
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 +
18666240*x^2 - 30643200*x
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 + 18666240*x^2 - 30643200*x
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 + 18666240*x^2 - 30643200*x
print g.vertex_connectivity() print h.vertex_connectivity() 
       
1
2
1
2
################################ # Figure 2.7: symmetry ################################ 
       
g=Graph('FJY}o') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('Fbo|w') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I,
9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I,
9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I, 9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I, 9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
print g.automorphism_group() print h.automorphism_group() 
       
Permutation Group with generators [(3,4), (1,2)(5,6)]
Permutation Group with generators [()]
Permutation Group with generators [(3,4), (1,2)(5,6)]
Permutation Group with generators [()]
################################ # Figure 2.8: planar ################################ 
       
g=Graph('G?CR^W') show(g) DL1=distLap(g) show(DL1) 
       

                                
                            

                                
h=Graph('G?Kpe[') show(h) DL2=distLap(h) show(DL2) 
       

                                
                            

                                
print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly() 
       
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?,
18.64776356080690?]
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?,
18.64776356080690?]
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 +
47349497*x^2 - 90671880*x
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 +
47349497*x^2 - 90671880*x
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?, 18.64776356080690?]
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?, 18.64776356080690?]
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 + 47349497*x^2 - 90671880*x
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 + 47349497*x^2 - 90671880*x
print g.is_planar() print h.is_planar() 
       
True
False
True
False
################################ # Lemma 3.8: permutations (14)(23) and (13)(24) are enough ################################ 
       
P=Permutations(4).list() L=[] for G in graphs(4): #iterates over all graphs on 4 vertices V=G.vertices() E=G.edges() for p in P: #iterates over all labels of the graph H=Graph(); H.add_vertices(range(4)); for e in E: H.add_edge(p[e[0]]-1,p[e[1]]-1) #Creating the base graph H if (0,1, None) not in H.edges() and (2,3, None) not in H.edges(): #edges we want to add need to not be in graph H1=H.copy(); H1.add_edge(0,1); H2=H.copy(); H2.add_edge(2,3); if H1.is_isomorphic(H2): #Check if isomorphic (hypothesis) J1=H1.copy(); J1.relabel({0:3, 1:2, 2:1, 3:0}); #The possible two permutations J2=H1.copy(); J2.relabel({0:2, 1:3, 2:0, 3:1}); if J1!=H2 and J2!=H2: #If the isomorphism was something else: a counter example L.append([H1, H2, H1.is_isomorphic(H2,certificate=True)[1]]) len(L) 
       
0
0
################################ # Theorem 3.9: matrix similarity ################################ 
       
a=var('a'); b=var('b'); c=var('c'); d=var('d'); e=var('e'); f=var('f'); h=var('h'); M=matrix([[a+b+c+d, -b, -c, -d], [-b, a+b+f+h, -f, -h], [-c, -f, a+c+f+e, -e], [-d, -h, -e, a+d+h+e]]) show(M) 
       

                                
                            

                                
C1=matrix([[1/2, 1/2, 1/2, -1/2], [1/2,1/2,-1/2,1/2], [1/2, -1/2, 1/2, 1/2], [-1/2, 1/2, 1/2, 1/2]]); show(C1) 
       

                                
                            

                                
show(C1*M*C1) 
       

                                
                            

                                
C2=matrix([[1/2, 1/2, -1/2, 1/2], [1/2,1/2,1/2,-1/2], [-1/2, 1/2, 1/2, 1/2], [1/2, -1/2, 1/2, 1/2]]); show(C2) 
       

                                
                            

                                
show(C2*M*C2) 
       

                                
                            

                                
################################ # Example 4.6: eigenvalues of SRG (29,14,6,7) ################################ 
       
g=graphs.CirculantGraph(29,[1, 4, 5, 6, 7, 9, 13]) show(g) 
       
DL=distLap(g) DL.eigenvalues() 
       
[0, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I]
[0, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I]
nn=29 kk=14 lam=6 mu=7 DLtheta=2*nn-kk+1/2*(lam-mu+sqrt((lam-mu)^2+4*(kk-mu))) DLtau=2*nn-kk+1/2*(lam-mu-sqrt((lam-mu)^2+4*(kk-mu))) mDLtheta=(1/2)*(nn-1-(2*kk+(nn-1)*(lam-mu))/sqrt((lam-mu)^2+4*(kk-mu))) mDLtau=(1/2)*(nn-1-(2*kk+(nn-1)*(lam-mu))/sqrt((lam-mu)^2+4*(kk-mu))) print DLtheta, n(DLtheta), mDLtheta print DLtau, n(DLtau), mDLtau 
       
1/2*sqrt(29) + 87/2 46.1925824035673 14
-1/2*sqrt(29) + 87/2 40.8074175964327 14
1/2*sqrt(29) + 87/2 46.1925824035673 14
-1/2*sqrt(29) + 87/2 40.8074175964327 14