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