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
|
|
def maxrho(n):
maxrho=0
for x in graphs.nauty_geng(str(n)+" -c"):
y=x.copy(immutable=True)
lambdas=InvTransDistLaplaQQ(y).eigenvalues()
lambdamax=max(lambdas)
if lambdamax==maxrho:
maxgraph.append(y.graph6_string())
if lambdamax>maxrho:
maxgraph=[]
maxrho=lambdamax
maxgraph.append(y.graph6_string())
print maxrho, maxgraph
|
|
def maxrhoAprox(n):
maxrho=0
for x in graphs.nauty_geng(str(n)+" -c"):
y=x.copy(immutable=True)
lambdas=InvTransDistLapla(y).eigenvalues()
lambdamax=max(lambdas)
if lambdamax==maxrho:
maxgraph.append(y.graph6_string())
if lambdamax>maxrho:
maxgraph=[]
maxrho=lambdamax
maxgraph.append(y.graph6_string())
print maxrho, maxgraph
|
|
def P(n):
G=graphs.PathGraph(n)
return G
|
|
maxrho(2)
2 ['A_'] 2 ['A_'] |
show(Graph('A_'))
|
### This is P_2
|
|
maxrho(3)
5/3 ['BW'] 5/3 ['BW'] |
show(Graph('BW'))
|
### This is P_3
|
|
maxrho(4)
1.614356776939085? ['CU'] 1.614356776939085? ['CU'] |
show(Graph('CU'))
|
### This is P_4
|
|
maxrho(5)
1.588637864772647? ['DQo'] 1.588637864772647? ['DQo'] |
show(Graph('DQo'))
|
### This is P_5
|
|
maxrho(6)
1.578353972780251? ['ECZO'] 1.578353972780251? ['ECZO'] |
show(Graph('ECZO'))
|
### This graph has larger spectral radius than P_6
max(InvTransDistLapla(P(6)).eigenvalues())
1.5755390124758006 1.5755390124758006 |
maxrho(7)
1.586481844076606? ['FCQrO'] 1.586481844076606? ['FCQrO'] |
show(Graph('FCQrO'))
|
### This graph has larger spectral radius than P_7
max(InvTransDistLapla(P(7)).eigenvalues())
1.5678373343557848 1.5678373343557848 |
maxrho(8)
1.590328449667252? ['GCOe`W'] 1.590328449667252? ['GCOe`W'] |
show(Graph('GCOe`W'))
|
### This graph has larger spectral radius than P_8
max(InvTransDistLapla(P(8)).eigenvalues())
1.5629205322022255 1.5629205322022255 |
maxrhoAprox(9)
1.59372387186 ['HCOcbQU'] 1.59372387186 ['HCOcbQU'] |
show(Graph('HCOcbQU'))
|
### This graph has larger spectral radius than P_9
max(InvTransDistLapla(P(9)).eigenvalues())
1.5595859273522232 1.5595859273522232 |
maxrhoAprox(10)
1.60331202958 ['ICOcaQqRO'] 1.60331202958 ['ICOcaQqRO'] |
show(Graph('ICOcaQqRO'))
|
### This graph has larger spectral radius than P_10
max(InvTransDistLapla(P(10)).eigenvalues())
1.5572186381687185 1.5572186381687185 |
### Define the graph family KPK
def KPK(x,y,z):
n = x+y+z-2
G = Graph(n)
for i in range(x):
for j in range(x):
if j>i:
G.add_edge(i,j)
for i in range(x-1, x+y-2):
G.add_edge(i,i+1)
for i in range(x+y-2, x+y+z-2):
for j in range(x+y-2, x+y+z-2):
if j>i:
G.add_edge(i,j)
return G
|
|
### We now show some KPK has larger spectral radius than P_n for n\leq 20
|
|
### n=11
max(InvTransDistLapla(KPK(4,5,4)).eigenvalues())>max(InvTransDistLapla(P(11)).eigenvalues())
True True |
### n=12
max(InvTransDistLapla(KPK(5,5,4)).eigenvalues())>max(InvTransDistLapla(P(12)).eigenvalues())
True True |
### n=13
max(InvTransDistLapla(KPK(5,5,5)).eigenvalues())>max(InvTransDistLapla(P(13)).eigenvalues())
True True |
### n=14
max(InvTransDistLapla(KPK(6,5,5)).eigenvalues())>max(InvTransDistLapla(P(14)).eigenvalues())
True True |
### n=15
max(InvTransDistLapla(KPK(6,5,6)).eigenvalues())>max(InvTransDistLapla(P(15)).eigenvalues())
True True |
### n=15
max(InvTransDistLapla(KPK(6,5,6)).eigenvalues())>max(InvTransDistLapla(P(15)).eigenvalues())
|
|
### n=16
max(InvTransDistLapla(KPK(6,6,6)).eigenvalues())>max(InvTransDistLapla(P(16)).eigenvalues())
True True |
### n=17
max(InvTransDistLapla(KPK(7,6,6)).eigenvalues())>max(InvTransDistLapla(P(17)).eigenvalues())
True True |
### n=18
max(InvTransDistLapla(KPK(7,6,7)).eigenvalues())>max(InvTransDistLapla(P(18)).eigenvalues())
True True |
### n=19
max(InvTransDistLapla(KPK(8,6,7)).eigenvalues())>max(InvTransDistLapla(P(19)).eigenvalues())
True True |
### n=20
max(InvTransDistLapla(KPK(8,6,8)).eigenvalues())>max(InvTransDistLapla(P(20)).eigenvalues())
True True |
### Spectral radius data for larger n: evidence that rho -> 2 as n becomes large
|
|
### n=15, example of pattern observed for n<=10 not holding
print max(InvTransDistLapla(KPK(6,5,6)).eigenvalues())
print max(InvTransDistLapla(KPK(6,5,6)).eigenvalues())>max(InvTransDistLapla(KPK(6,6,5)).eigenvalues())
1.63407962857 True 1.63407962857 True |
### n=20
max(InvTransDistLapla(KPK(8,6,8)).eigenvalues())
1.660621987709971 1.660621987709971 |
max(InvTransDistLapla(KPK(10,7,10)).eigenvalues())
1.6823988465386899 1.6823988465386899 |
max(InvTransDistLapla(KPK(21,10,21)).eigenvalues())
1.7483017575703617 1.7483017575703617 |
max(InvTransDistLapla(KPK(43,16,43)).eigenvalues())
1.80811033797491 1.80811033797491 |
max(InvTransDistLapla(KPK(90,22,90)).eigenvalues())
1.8565971490863098 1.8565971490863098 |
max(InvTransDistLapla(KPK(184,34,184)).eigenvalues())
1.8946858906277024 1.8946858906277024 |
max(InvTransDistLapla(KPK(280,42,280)).eigenvalues())
1.9125383648659866 1.9125383648659866 |
max(InvTransDistLapla(KPK(377,48,377)).eigenvalues())
1.9235081972085837 1.9235081972085837 |
def minrho(n):
minrho=3
for x in graphs.nauty_geng(str(n)+" -c"):
y=x.copy(immutable=True)
lambdas=InvTransDistLapla(y).eigenvalues()
lambdamax=max(lambdas)
if lambdamax==minrho:
mingraph.append(y.graph6_string())
if lambdamax<minrho:
mingraph=[]
minrho=lambdamax
mingraph.append(y.graph6_string())
print minrho, mingraph
|
|
minrho(3)
1.5 ['Bw'] 1.5 ['Bw'] |
min3=Graph('Bw')
show(min3)
print min3.degree_sequence()
[2, 2, 2] [2, 2, 2] 
|
minrho(4)
1.33333333333 ['C~'] 1.33333333333 ['C~'] |
min4=Graph('C~')
show(min4)
print min4.degree_sequence()
[3, 3, 3, 3] [3, 3, 3, 3] 
|
minrho(5)
1.25 + 5.55111512313e-17*I ['D~{']
1.25 + 5.55111512313e-17*I ['D~{']
|
min5=Graph('D~{')
show(min5)
print min5.degree_sequence()
[4, 4, 4, 4, 4] [4, 4, 4, 4, 4] 
|
minrho(6)
1.2 ['E~~w'] 1.2 ['E~~w'] |
min6=Graph('E~~w')
show(min6)
print min6.degree_sequence()
[5, 5, 5, 5, 5, 5] [5, 5, 5, 5, 5, 5] 
|
minrho(7)
1.16666666667 + 1.11022302463e-16*I ['F~~~w'] 1.16666666667 + 1.11022302463e-16*I ['F~~~w'] |
min7=Graph('F~~~w')
show(min7)
print min7.degree_sequence()
[6, 6, 6, 6, 6, 6, 6] [6, 6, 6, 6, 6, 6, 6] 
|
minrho(8)
1.14285714286 ['G~~~~{']
1.14285714286 ['G~~~~{']
|
min8=Graph('G~~~~{')
show(min8)
print min8.degree_sequence()
[7, 7, 7, 7, 7, 7, 7, 7] [7, 7, 7, 7, 7, 7, 7, 7] 
|
minrho(9)
1.125 ['H~~~~~~'] 1.125 ['H~~~~~~'] |
min9=Graph('H~~~~~~')
show(min9)
print min9.degree_sequence()
[8, 8, 8, 8, 8, 8, 8, 8, 8] [8, 8, 8, 8, 8, 8, 8, 8, 8] 
|
minrho(10)
1.11111111111 ['I~~~~~~~w'] 1.11111111111 ['I~~~~~~~w'] |
min10=Graph('I~~~~~~~w')
show(min10)
print min10.degree_sequence()
[9, 9, 9, 9, 9, 9, 9, 9, 9, 9] [9, 9, 9, 9, 9, 9, 9, 9, 9, 9] 
|
|
|