NormDistLapla-Cospec10

1815 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 
       
### Sorting the graphs in to groups of potentially cospectral graphs 
       
Num1 = 545 Num2 = 5279 Num_Vertices = 10 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.00005 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 
       
len(N) 
       
38164
38164
### Checking each of these pairs at another prime 
       
epsilon=0.000005 Q=[] for i in range(len(N)): G1=Graph(N[i][0]) G2=Graph(N[i][1]) C1=InvTransDistLapla(G1).charpoly()(71) C2=InvTransDistLapla(G2).charpoly()(71) if abs(C1-C2)<epsilon: Q.append(N[i]) 
       
len(Q) 
       
8232
8232
### Checking each of these pairs for cospectrality 
       
Q1=[] for i in range(len(Q)): G1=Graph(Q[i][0]) G2=Graph(Q[i][1]) C1=InvTransDistLaplaQQ(G1).charpoly() C2=InvTransDistLaplaQQ(G2).charpoly() if C1-C2==0: Q1.append(Q[i]) 
       
len(Q1) 
       
3775
3775
### Computing the number of unique graphs in the list GraphsWithMates=[] for i in range(len(Q1)): if Q1[i][0] not in GraphsWithMates: GraphsWithMates.append(Q1[i][0]) if Q1[i][1] not in GraphsWithMates: GraphsWithMates.append(Q1[i][1]) print len(GraphsWithMates) 
       
7538
7538
### None of the graphs are bipartite for i in range(len(GraphsWithMates)): if Graph(GraphsWithMates[i]).is_bipartite==True: print GraphsWithMates[i] 
       
### Checking for multiples for i in range(len(Q1)): for j in range(i+1,len(Q1)): if (Q1[i][0] in Q1[j]) or (Q1[i][1] in Q1[j]): print Q1[i],Q1[j] 
       
['IrELJFHN?', 'IbFLJFHN?'] ['IrELJFHN?', 'IbELjFHN?']
['IrELJFHN?', 'IbFLJFHN?'] ['IbFLJFHN?', 'IbELjFHN?']
['IrELJFHN?', 'IbELjFHN?'] ['IbFLJFHN?', 'IbELjFHN?']
['IjC{HVGgo', 'IbC{HVHgo'] ['IjC{HVGgo', 'IfHYKEJIo']
['IjC{HVGgo', 'IbC{HVHgo'] ['IbC{HVHgo', 'IfHYKEJIo']
['IjC{HVGgo', 'IfHYKEJIo'] ['IbC{HVHgo', 'IfHYKEJIo']
['Ib[]JMihW', 'Id[IxNpxO'] ['Ib[]JMihW', 'IdsihfFZO']
['Ib[]JMihW', 'Id[IxNpxO'] ['Id[IxNpxO', 'IdsihfFZO']
['Ib[]JMihW', 'IdsihfFZO'] ['Id[IxNpxO', 'IdsihfFZO']
['IbNileJmG', 'IvWYjULhW'] ['IbNileJmG', 'IfY[XfhYo']
['IbNileJmG', 'IvWYjULhW'] ['IvWYjULhW', 'IfY[XfhYo']
['IbNileJmG', 'IfY[XfhYo'] ['IvWYjULhW', 'IfY[XfhYo']
['IrELJFHN?', 'IbFLJFHN?'] ['IrELJFHN?', 'IbELjFHN?']
['IrELJFHN?', 'IbFLJFHN?'] ['IbFLJFHN?', 'IbELjFHN?']
['IrELJFHN?', 'IbELjFHN?'] ['IbFLJFHN?', 'IbELjFHN?']
['IjC{HVGgo', 'IbC{HVHgo'] ['IjC{HVGgo', 'IfHYKEJIo']
['IjC{HVGgo', 'IbC{HVHgo'] ['IbC{HVHgo', 'IfHYKEJIo']
['IjC{HVGgo', 'IfHYKEJIo'] ['IbC{HVHgo', 'IfHYKEJIo']
['Ib[]JMihW', 'Id[IxNpxO'] ['Ib[]JMihW', 'IdsihfFZO']
['Ib[]JMihW', 'Id[IxNpxO'] ['Id[IxNpxO', 'IdsihfFZO']
['Ib[]JMihW', 'IdsihfFZO'] ['Id[IxNpxO', 'IdsihfFZO']
['IbNileJmG', 'IvWYjULhW'] ['IbNileJmG', 'IfY[XfhYo']
['IbNileJmG', 'IvWYjULhW'] ['IvWYjULhW', 'IfY[XfhYo']
['IbNileJmG', 'IfY[XfhYo'] ['IvWYjULhW', 'IfY[XfhYo']
### 4 sets of triples, they account for 12 pairs. The other 3763 pairs are just pairs 
       
### Examples 
       
A1=Graph('IboJhUHwW') A2=Graph('In`W[]?Yg') B1=Graph('I~vz|~n}w') B2=Graph('IbCIHEHh?') C1=Graph('IjdiLeZj_') C2=Graph('IrW^KNXNO') 
       
### Planarity not preserved 
       
show(A1) NDL1=NormDistLaplaSR(A1) show(NDL1) 
       

                                
                            

                                
show(A2) NDL1=NormDistLaplaSR(A2) show(NDL1) 
       

                                
                            

                                
InvTransDistLaplaQQ(A1).charpoly()-InvTransDistLaplaQQ(A2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(A1).eigenvalues() print InvTransDistLaplaQQ(A1).charpoly() 
       
[0, 0.9499405205094519?, 1.034138806358918?, 1.089399173994262?,
1.094876750363498?, 1.227825576627504?, 1.254568759112661?,
1.316535354237667?, 1.007439500303720? + 0.?e-37*I, 1.025275558492321? +
0.?e-33*I]
x^10 - 10*x^9 + 11760575/264992*x^8 - 14698252437/128107070*x^7 +
1561159495967/8198852480*x^6 - 5605798973451/26646270560*x^5 +
7068694654043/45679320960*x^4 - 11682868723247/159877623360*x^3 +
535639931153/26646270560*x^2 - 65401424433/26646270560*x
[0, 0.9499405205094519?, 1.034138806358918?, 1.089399173994262?, 1.094876750363498?, 1.227825576627504?, 1.254568759112661?, 1.316535354237667?, 1.007439500303720? + 0.?e-37*I, 1.025275558492321? + 0.?e-33*I]
x^10 - 10*x^9 + 11760575/264992*x^8 - 14698252437/128107070*x^7 + 1561159495967/8198852480*x^6 - 5605798973451/26646270560*x^5 + 7068694654043/45679320960*x^4 - 11682868723247/159877623360*x^3 + 535639931153/26646270560*x^2 - 65401424433/26646270560*x
### Planarity not preserved print A1.is_planar() print A2.is_planar() 
       
True
False
True
False
### different girth, Weiner indexes, k-regularity, k-transmission regularity and are only NDL-cospectral 
       
show(B1) NDL1=NormDistLaplaSR(B1) show(NDL1) 
       

                                
                            

                                
show(B2) NDL1=NormDistLaplaSR(B2) show(NDL1) 
       

                                
                            

                                
InvTransDistLaplaQQ(B1).charpoly()-InvTransDistLaplaQQ(B2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(B1).eigenvalues() print InvTransDistLaplaQQ(B1).charpoly() 
       
[0, 1, 1, 1, 1, 6/5, 6/5, 6/5, 6/5, 6/5]
x^10 - 10*x^9 + 222/5*x^8 - 2872/25*x^7 + 23861/125*x^6 -
660126/3125*x^5 + 486504/3125*x^4 - 230256/3125*x^3 + 63504/3125*x^2 -
7776/3125*x
[0, 1, 1, 1, 1, 6/5, 6/5, 6/5, 6/5, 6/5]
x^10 - 10*x^9 + 222/5*x^8 - 2872/25*x^7 + 23861/125*x^6 - 660126/3125*x^5 + 486504/3125*x^4 - 230256/3125*x^3 + 63504/3125*x^2 - 7776/3125*x
### B2 is a subgraph of B1 B1.subgraph_search(B2) 
       
### Girth not preserved print B1.girth() print B2.girth() 
       
3
5
3
5
### Weiner index not preserved print B1.wiener_index() print B2.wiener_index() 
       
50
75
50
75
### k-regularity not preserved print B1.degree_sequence() print B2.degree_sequence() 
       
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
### k-transmission regularity not preserved print trs(B1) print trs(B2) 
       
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
[15, 15, 15, 15, 15, 15, 15, 15, 15, 15]
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
[15, 15, 15, 15, 15, 15, 15, 15, 15, 15]
### Graphs which are cospectral for all 8 matrices 
       
show(C1) NDL1=NormDistLaplaSR(C1) show(NDL1) 
       

                                
                            

                                
show(C2) NDL1=NormDistLaplaSR(C2) show(NDL1) 
       

                                
                            

                                
InvTransDistLaplaQQ(C1).charpoly()-InvTransDistLaplaQQ(C2).charpoly() 
       
0
0
print InvTransDistLaplaQQ(C1).eigenvalues() print InvTransDistLaplaQQ(C1).charpoly() 
       
[0, 15/13, 15/13, 1.029382000865393?, 1.201387229903838?,
0.90713856743900?, 0.96547965784461?, 1.06051171486520?,
1.2446875525731?, 1.28372096881659?]
x^10 - 10*x^9 + 7500/169*x^8 - 252026/2197*x^7 + 5436076/28561*x^6 -
78049160/371293*x^5 + 745908617/4826809*x^4 - 4575468034/62748517*x^3 +
16346031420/815730721*x^2 - 25912467900/10604499373*x
[0, 15/13, 15/13, 1.029382000865393?, 1.201387229903838?, 0.90713856743900?, 0.96547965784461?, 1.06051171486520?, 1.2446875525731?, 1.28372096881659?]
x^10 - 10*x^9 + 7500/169*x^8 - 252026/2197*x^7 + 5436076/28561*x^6 - 78049160/371293*x^5 + 745908617/4826809*x^4 - 4575468034/62748517*x^3 + 16346031420/815730721*x^2 - 25912467900/10604499373*x
print C1.degree_sequence() print C2.degree_sequence() 
       
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
print trs(C1) print trs(C2) 
       
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
[13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
print C1.diameter() print C2.diameter() 
       
2
2
2
2