Spectral radius data

1816 days ago by reinh196

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]