DistanceSpectra

3360 days ago by chlin

# This file provides Sage code cited in the paper "On the distance spectra of graphs" # by Ghodratollah Aalipour, Aida Abiad, Zhanar Berikkyzy, Jay Cummings, Jessica De Silva, Wei Gao, # Kristin Heysse, Leslie Hogben, Franklin H.J. Kenter, Jephian C.-H. Lin, Michael Tait # Contents # 1) Distance eigenvalues of the Shrikhande graph (for Theorem 3.4) # 2) Distance eigenvalues of individual graphs that have one postive distance eigenvalue (for Proposition 3.1) # 3) Every tree T of order at most 20 has at least diam(T)+1 distinct distance eigenvalues (for Questiopn 4.6) 
       
# Distance eigenvalues of the Shrikhande graph g=graphs.ShrikhandeGraph() show(g) d=g.distance_matrix() print d d.eigenvalues() 
       
[0 1 1 2 2 2 1 1 2 1 2 2 2 2 2 1]
[1 0 1 1 2 2 2 1 1 2 1 2 2 2 2 2]
[1 1 0 1 1 2 2 2 2 1 2 1 2 2 2 2]
[2 1 1 0 1 1 2 2 2 2 1 2 1 2 2 2]
[2 2 1 1 0 1 1 2 2 2 2 1 2 1 2 2]
[2 2 2 1 1 0 1 1 2 2 2 2 1 2 1 2]
[1 2 2 2 1 1 0 1 2 2 2 2 2 1 2 1]
[1 1 2 2 2 1 1 0 1 2 2 2 2 2 1 2]
[2 1 2 2 2 2 2 1 0 2 1 1 2 1 1 2]
[1 2 1 2 2 2 2 2 2 0 2 1 1 2 1 1]
[2 1 2 1 2 2 2 2 1 2 0 2 1 1 2 1]
[2 2 1 2 1 2 2 2 1 1 2 0 2 1 1 2]
[2 2 2 1 2 1 2 2 2 1 1 2 0 2 1 1]
[2 2 2 2 1 2 1 2 1 2 1 1 2 0 2 1]
[2 2 2 2 2 1 2 1 1 1 2 1 1 2 0 2]
[1 2 2 2 2 2 1 2 2 1 1 2 1 1 2 0]
[24, -4, -4, -4, -4, -4, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0 1 1 2 2 2 1 1 2 1 2 2 2 2 2 1]
[1 0 1 1 2 2 2 1 1 2 1 2 2 2 2 2]
[1 1 0 1 1 2 2 2 2 1 2 1 2 2 2 2]
[2 1 1 0 1 1 2 2 2 2 1 2 1 2 2 2]
[2 2 1 1 0 1 1 2 2 2 2 1 2 1 2 2]
[2 2 2 1 1 0 1 1 2 2 2 2 1 2 1 2]
[1 2 2 2 1 1 0 1 2 2 2 2 2 1 2 1]
[1 1 2 2 2 1 1 0 1 2 2 2 2 2 1 2]
[2 1 2 2 2 2 2 1 0 2 1 1 2 1 1 2]
[1 2 1 2 2 2 2 2 2 0 2 1 1 2 1 1]
[2 1 2 1 2 2 2 2 1 2 0 2 1 1 2 1]
[2 2 1 2 1 2 2 2 1 1 2 0 2 1 1 2]
[2 2 2 1 2 1 2 2 2 1 1 2 0 2 1 1]
[2 2 2 2 1 2 1 2 1 2 1 1 2 0 2 1]
[2 2 2 2 2 1 2 1 1 1 2 1 1 2 0 2]
[1 2 2 2 2 2 1 2 2 1 1 2 1 1 2 0]
[24, -4, -4, -4, -4, -4, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
## Function to show {eigenvalue: multiplicity} def eigens_multi(A,radical=False): """ Input: matrix A; Output: the dictionary of {eigenvalues: multiplicity}; """ if radical==True: A=A.change_ring(SR); l=A.eigenvalues(); eigens={}; for i in l: eigens[i]=0; for i in l: eigens[i]+=1; return eigens; 
       
## Setting up the graphs. G=[0]*6; G[0]=graphs.GossetGraph(); #Replaced by the next line for Sage 6.7 or older version. #G[0]=Graph("w~~~~rt{~Z\\ZxnvYZYmlfrb}|hDuhLlcmmMNf_^zzQGNYcP\\kcRZbaJjoNBx{?N~o^}?A`}F_Kbbm_[QZ\\_]Cj\\oN_dm{BzB{?]WIMM@tPQRYBYRPIuAyJgQv?|Bxb_M[kWIR@jTQcciDjShXCkFMgpwqBKxeKoS`TYqdTCcKtkdKwWQXrbEZ@OdUmITZ@_e[{KXn?YPABzvY?IcO`zvYg@caC\\zlf?BaGR]zb{?@wOjv`~w??N_n_~~w???^_^~~{"); G[1]=graphs.SchlaefliGraph(); G[2]=graphs.chang_graphs(); #Replaced by the next line for Sage 6.7 or older version. #G[2]=[Graph("[}~~EebhkrRb_~SoLOIiAZ?LBBxDb?bQcggjHKEwoZFAaiZ?Yf[?dxb@@tdWGkwn"),Graph("[~z^UipkkZPr_~Y_LOIiATOLBBxPR@`acoojBBSoWXTaabN?Yts?Yji_QyioClXZ"),Graph("[~~vVMWdKFpV`^UGIaIERQ`\\DBxpA@g`CbGRI`AxICNaFM[?fM\\?Ytj@CxrGGlYt")]; G[3]=graphs.IcosahedralGraph(); G[4]=graphs.PetersenGraph(); G[5]=graphs.DodecahedralGraph(); 
       
print "(II) the Gosset Graph:",eigens_multi(G[0].distance_matrix()); print "(III) the Schlaefli Graph:",eigens_multi(G[1].distance_matrix()); print "(VI) the three Chang Graphs:",eigens_multi(G[2][0].distance_matrix()),eigens_multi(G[2][1].distance_matrix()),eigens_multi(G[2][2].distance_matrix()); print "(IX) the icosahedral Graph:",eigens_multi(G[3].distance_matrix()); print "(XII) the Petersen Graph:",eigens_multi(G[4].distance_matrix()); print "(XIII) the dodecahedral Graph:",eigens_multi(G[5].distance_matrix()); ##Check some numerical values. print ; print "Checking numerical values:" a=eigens_multi(G[3].distance_matrix()).keys(); a.sort(); b=eigens_multi(G[5].distance_matrix()).keys(); b.sort(); print a[0],"=","-3-sqrt(5)?",a[0]==QQbar(-3-sqrt(5)); print a[1],"=","-3+sqrt(5)?",a[1]==QQbar(-3+sqrt(5)); print b[0],"=","-7-3*sqrt(5)?",b[0]==QQbar(-7-3*sqrt(5)); print b[2],"=","-7+3*sqrt(5)?",b[2]==QQbar(-7+3*sqrt(5)); 
       
(II) the Gosset Graph: {0: 48, -12: 7, 84: 1}
(III) the Schlaefli Graph: {0: 20, -6: 6, 36: 1}
(VI) the three Chang Graphs: {0: 20, 42: 1, -6: 7} {0: 20, 42: 1, -6: 7}
{0: 20, 42: 1, -6: 7}
(IX) the icosahedral Graph: {-0.763932022500211?: 3,
-5.236067977499789?: 3, 18: 1, 0: 5}
(XII) the Petersen Graph: {0: 4, -3: 5, 15: 1}
(XIII) the dodecahedral Graph: {-2: 4, 50: 1, -13.70820393249937?: 3,
-0.2917960675006309?: 3, 0: 9}

Checking numerical values:
-5.236067977499789? = -3-sqrt(5)? True
-0.763932022500211? = -3+sqrt(5)? True
-13.70820393249937? = -7-3*sqrt(5)? True
-0.2917960675006309? = -7+3*sqrt(5)? True
(II) the Gosset Graph: {0: 48, -12: 7, 84: 1}
(III) the Schlaefli Graph: {0: 20, -6: 6, 36: 1}
(VI) the three Chang Graphs: {0: 20, 42: 1, -6: 7} {0: 20, 42: 1, -6: 7} {0: 20, 42: 1, -6: 7}
(IX) the icosahedral Graph: {-0.763932022500211?: 3, -5.236067977499789?: 3, 18: 1, 0: 5}
(XII) the Petersen Graph: {0: 4, -3: 5, 15: 1}
(XIII) the dodecahedral Graph: {-2: 4, 50: 1, -13.70820393249937?: 3, -0.2917960675006309?: 3, 0: 9}

Checking numerical values:
-5.236067977499789? = -3-sqrt(5)? True
-0.763932022500211? = -3+sqrt(5)? True
-13.70820393249937? = -7-3*sqrt(5)? True
-0.2917960675006309? = -7+3*sqrt(5)? True
## Function for finding the number of distinct eigenvalues. def distinct_eigens(A,dgable=True): if dgable==True: return A.minimal_polynomial().degree(); if dgable==False: return len(set(g.distance_matrix().eigenvalues())); 
       
## Check if q_D(T) >= diam(T)+1 for trees. print "Print \"n done\" if there is no tree on n vertices with q_D(T)<diam(T)+1"; for n in range(1,21): for T in graphs.nauty_geng("%s %s:%s -c"%(n,n-1,n-1)): if distinct_eigens(T.distance_matrix())<T.diameter()+1: print T.graph6_string(); print n, "done"; 
       
Print "n done" if there is no tree on n vertices with
q_D(T)<diam(T)+1
1 done
2 done
3 done
4 done
5 done
6 done
7 done
8 done
9 done
10 done
11 done
12 done
13 done
14 done
15 done
16 done
17 done
18 done
19 done
20 done
Print "n done" if there is no tree on n vertices with q_D(T)<diam(T)+1
1 done
2 done
3 done
4 done
5 done
6 done
7 done
8 done
9 done
10 done
11 done
12 done
13 done
14 done
15 done
16 done
17 done
18 done
19 done
20 done