NormDistLapla-Cospec9

1816 days ago by reinh196

### Defining the matrices for various rings 
       
def distLapla(G): n=G.order() M=zero_matrix(RDF,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=-x M[j,i]=-x M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x return M def InvTransMatrix(G): n=G.order() M=zero_matrix(RDF,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=0 M[j,i]=0 M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x for i in range(n): M[i,i]=M[i,i]^(-1) return M def InvTransDistLapla(G): M=InvTransMatrix(G)*distLapla(G) return M def distLaplaQQ(G): n=G.order() M=zero_matrix(QQ,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=-x M[j,i]=-x M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x return M def InvTransMatrixQQ(G): n=G.order() M=zero_matrix(QQ,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=0 M[j,i]=0 M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x for i in range(n): M[i,i]=M[i,i]^(-1) return M def InvTransDistLaplaQQ(G): M=InvTransMatrixQQ(G)*distLaplaQQ(G) return M def distLaplaSR(G): n=G.order() M=zero_matrix(SR,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=-x M[j,i]=-x M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x return M def HalfInvTransMatrixSR(G): n=G.order() M=zero_matrix(SR,n,n) for i in range(n): for j in range(i+1,n): x=G.distance(i,j) M[i,j]=0 M[j,i]=0 M[i,i]=M[i,i]+x M[j,j]=M[j,j]+x for i in range(n): M[i,i]=M[i,i]^(-1/2) return M def NormDistLaplaSR(G): M=HalfInvTransMatrixSR(G)*distLaplaSR(G)*HalfInvTransMatrixSR(G) return M 
       
# 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 
       
### Sorting the graphs in to groups of potentially cospectral graphs 
       
Num1 = 545 Num2 = 2741 Num_Vertices = 9 L = [] for i in range(Num2): L.append([i,[]]) for G in graphs(Num_Vertices): if G.is_connected(): a=InvTransDistLapla(G).charpoly()(Num1) b = mod(a.floor(), Num2) if G.graph6_string() not in L[b][1]: L[b][1].append(G.graph6_string()) c = mod(a.ceil(), Num2) if G.graph6_string() not in L[c][1]: L[c][1].append(G.graph6_string()) 
       
### Checking within each group for pairs with similar characteristic polynomial evaluated at a prime 
       
epsilon=0.0000005 N=[] for i in range(Num2): K=[] M=[] for j in range(len(L[i][1])): a=InvTransDistLapla(Graph(L[i][1][j])).charpoly()(167) K.append([L[i][1][j],a]) for i in range(len(K)): for j in range(i+1,len(K)): if abs(K[i][1]-K[j][1])<epsilon: N.append([K[i][0],K[j][0]]) print N 
       
[['Hld}JEh', 'H|C}ZEX'], ['HnsmHmN', 'HnujHeN'], ['H|UgIUF', 'H|SgIUN'],
['HnVyKEB', 'HnS}kEB'], ['HlDnXeH', 'HltihFH'], ['HxEwk^_', 'HnTyKEB'],
['H|diXUX', 'HldzKeL'], ['HnCi\\fN', 'H|YX]eU'], ['HnKikEL', 'HnHG^E['],
['H~uj~Uz', 'H~vj|~j'], ['HnVykEB', 'HnU}kEB'], ['HnDLHuH', 'HnCmJUH'],
['HhShMUU', 'HlsgjEB'], ['Hh]gMEV', 'HnSk\\EB'], ['HnUg}Eb', 'HlS}LFL'],
['H|SgIef', 'HlcijeH']]
[['Hld}JEh', 'H|C}ZEX'], ['HnsmHmN', 'HnujHeN'], ['H|UgIUF', 'H|SgIUN'], ['HnVyKEB', 'HnS}kEB'], ['HlDnXeH', 'HltihFH'], ['HxEwk^_', 'HnTyKEB'], ['H|diXUX', 'HldzKeL'], ['HnCi\\fN', 'H|YX]eU'], ['HnKikEL', 'HnHG^E['], ['H~uj~Uz', 'H~vj|~j'], ['HnVykEB', 'HnU}kEB'], ['HnDLHuH', 'HnCmJUH'], ['HhShMUU', 'HlsgjEB'], ['Hh]gMEV', 'HnSk\\EB'], ['HnUg}Eb', 'HlS}LFL'], ['H|SgIef', 'HlcijeH']]
### Checking each of these pairs for cospectrality 
       
for i in range(0,len(N)): G1=Graph(N[i][0]) G2=Graph(N[i][1]) C1=InvTransDistLaplaQQ(G1).charpoly() C2=InvTransDistLaplaQQ(G2).charpoly() if C1-C2==0: print N[i] 
       
['HnVyKEB', 'HnS}kEB']
['HxEwk^_', 'HnTyKEB']
['H~uj~Uz', 'H~vj|~j']
['HnVykEB', 'HnU}kEB']
['HnVyKEB', 'HnS}kEB']
['HxEwk^_', 'HnTyKEB']
['H~uj~Uz', 'H~vj|~j']
['HnVykEB', 'HnU}kEB']
#### Cospectral Graphs on 9 Vertices 
       
A1=Graph('HxEwk^_') A2=Graph('HnTyKEB') B1=Graph('HnVyKEB') B2=Graph('HnS}kEB') C1=Graph('HnU}kEB') C2=Graph('HnVykEB') D1=Graph('H~uj~Uz') D2=Graph('H~vj|~j') 
       
#### A1 and A2 
       
show(A1) NDL1=NormDistLaplaSR(A1) show(NDL1) 
       

                                
                            

                                
show(A2) NDL2=NormDistLaplaSR(A2) show(NDL2) 
       

                                
                            

                                
InvTransDistLaplaQQ(A1).charpoly()-InvTransDistLaplaQQ(A2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(A1).eigenvalues() print InvTransDistLaplaQQ(A1).charpoly() 
       
[17/15, 16/15, 0, 1.033863908438321?, 1.223711849137437?,
0.986500310092595?, 1.03206847777995?, 1.113802831792652?,
1.410052622759050?]
x^9 - 9*x^8 + 1926013/54450*x^7 - 259072321/3267000*x^6 +
2717888893/24502500*x^5 - 233194363/2352240*x^4 +
243851297233/4410450000*x^3 - 587831111/33412500*x^2 +
674126228/275653125*x
[17/15, 16/15, 0, 1.033863908438321?, 1.223711849137437?, 0.986500310092595?, 1.03206847777995?, 1.113802831792652?, 1.410052622759050?]
x^9 - 9*x^8 + 1926013/54450*x^7 - 259072321/3267000*x^6 + 2717888893/24502500*x^5 - 233194363/2352240*x^4 + 243851297233/4410450000*x^3 - 587831111/33412500*x^2 + 674126228/275653125*x
distLaplaQQ(A1).charpoly() 
       
x^9 - 116*x^8 + 5853*x^7 - 167806*x^6 + 2990335*x^5 - 33920980*x^4 +
239222875*x^3 - 959072786*x^2 + 1673692704*x
x^9 - 116*x^8 + 5853*x^7 - 167806*x^6 + 2990335*x^5 - 33920980*x^4 + 239222875*x^3 - 959072786*x^2 + 1673692704*x
#### B1 and B2 
       
show(B1) NDL1=NormDistLaplaSR(B1) show(NDL1) 
       

                                
                            

                                
show(B2) NDL2=NormDistLaplaSR(B2) show(NDL2) 
       

                                
                            

                                
InvTransDistLaplaQQ(B1).charpoly()-InvTransDistLaplaQQ(B2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(B1).eigenvalues() print InvTransDistLaplaQQ(B1).charpoly() 
       
[17/15, 11/10, 16/15, 0, 0.96784697705089?, 1.0292391022636?,
1.0953703206547?, 1.20206869706400?, 1.40547490296680?]
x^9 - 9*x^8 + 1926211/54450*x^7 - 9598153/121000*x^6 +
1812984073/16335000*x^5 - 24314025553/245025000*x^4 +
67829453381/1225125000*x^3 - 10796929657/612562500*x^2 + 758404/309375*x
[17/15, 11/10, 16/15, 0, 0.96784697705089?, 1.0292391022636?, 1.0953703206547?, 1.20206869706400?, 1.40547490296680?]
x^9 - 9*x^8 + 1926211/54450*x^7 - 9598153/121000*x^6 + 1812984073/16335000*x^5 - 24314025553/245025000*x^4 + 67829453381/1225125000*x^3 - 10796929657/612562500*x^2 + 758404/309375*x
distLaplaQQ(B1).charpoly() 
       
x^9 - 114*x^8 + 5648*x^7 - 158862*x^6 + 2774997*x^5 - 30830726*x^4 +
212786586*x^3 - 834230170*x^2 + 1422606240*x
x^9 - 114*x^8 + 5648*x^7 - 158862*x^6 + 2774997*x^5 - 30830726*x^4 + 212786586*x^3 - 834230170*x^2 + 1422606240*x
#### C1 and C2 
       
show(C1) NDL1=NormDistLaplaSR(C1) show(NDL1) 
       

                                
                            

                                
show(C2) NDL2=NormDistLaplaSR(C2) show(NDL2) 
       

                                
                            

                                
InvTransDistLaplaQQ(C1).charpoly()-InvTransDistLaplaQQ(C2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(C1).eigenvalues() print InvTransDistLaplaQQ(C1).charpoly() 
       
[7/5, 13/11, 17/15, 157/165, 0, 11/10, 11/10, 16/15, 16/15]
x^9 - 9*x^8 + 3852769/108900*x^7 - 21601501/272250*x^6 +
27208546/245025*x^5 - 6083465273/61256250*x^4 +
11318237801/204187500*x^3 - 1228870232/69609375*x^2 + 15544256/6328125*x
[7/5, 13/11, 17/15, 157/165, 0, 11/10, 11/10, 16/15, 16/15]
x^9 - 9*x^8 + 3852769/108900*x^7 - 21601501/272250*x^6 + 27208546/245025*x^5 - 6083465273/61256250*x^4 + 11318237801/204187500*x^3 - 1228870232/69609375*x^2 + 15544256/6328125*x
distLaplaQQ(C1).charpoly() 
       
x^9 - 112*x^8 + 5447*x^7 - 150274*x^6 + 2572751*x^5 - 27995116*x^4 +
189113161*x^3 - 725242914*x^2 + 1209121056*x
x^9 - 112*x^8 + 5447*x^7 - 150274*x^6 + 2572751*x^5 - 27995116*x^4 + 189113161*x^3 - 725242914*x^2 + 1209121056*x
#### D1 and D2 
       
show(D1) NDL1=NormDistLaplaSR(D1) show(NDL1) 
       

                                
                            

                                
show(D2) NDL2=NormDistLaplaSR(D2) show(NDL2) 
       

                                
                            

                                
InvTransDistLaplaQQ(D1).charpoly()-InvTransDistLaplaQQ(D2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(D1).eigenvalues() print InvTransDistLaplaQQ(D1).charpoly() 
       
[14/15, 0, 6/5, 6/5, 1, 1, 11/9, 11/9, 11/9]
x^9 - 9*x^8 + 23884/675*x^7 - 7232482/91125*x^6 + 30369859/273375*x^5 -
27161183/273375*x^4 + 15156922/273375*x^3 - 1608332/91125*x^2 +
74536/30375*x
[14/15, 0, 6/5, 6/5, 1, 1, 11/9, 11/9, 11/9]
x^9 - 9*x^8 + 23884/675*x^7 - 7232482/91125*x^6 + 30369859/273375*x^5 - 27161183/273375*x^4 + 15156922/273375*x^3 - 1608332/91125*x^2 + 74536/30375*x
### Different number of edges print D1.size() print D2.size() 
       
28
30
28
30
### Different degree sequence print D1.degree_sequence() print D2.degree_sequence() 
       
[7, 7, 7, 7, 6, 6, 6, 6, 4]
[7, 7, 7, 7, 7, 7, 6, 6, 6]
[7, 7, 7, 7, 6, 6, 6, 6, 4]
[7, 7, 7, 7, 7, 7, 6, 6, 6]
### Different transmission sequence print trs(D1) print trs(D2) 
       
[9, 9, 9, 9, 10, 10, 10, 10, 12]
[9, 9, 9, 9, 9, 9, 10, 10, 10]
[9, 9, 9, 9, 10, 10, 10, 10, 12]
[9, 9, 9, 9, 9, 9, 10, 10, 10]
### Different distance laplacian eigenvalues distLaplaQQ(D1).charpoly()-distLaplaQQ(D2).charpoly() 
       
-4*x^8 + 297*x^7 - 9432*x^6 + 166070*x^5 - 1750764*x^4 + 11050929*x^3 -
38669400*x^2 + 57865104*x
-4*x^8 + 297*x^7 - 9432*x^6 + 166070*x^5 - 1750764*x^4 + 11050929*x^3 - 38669400*x^2 + 57865104*x