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