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