BDGLRSY18-Distance_Laplacian -- Sage

# This worksheet contains verifications used in the paper # Graphs that are cospectral for the distance Laplacian # by Boris Brimkov, Ken Duna, Leslie Hogben, Kate Lorenzen, Carolyn Reinhart, Sung-Yell Song, and Mark Yarrow

################################ # Definitions of Sage functions ################################

# Definition of Distance Laplacian def distLap(G): n=G.order() ones = ones_matrix(n,1) dg=G.distance_matrix() trg=dg*ones DL=diagonal_matrix(vector(trg))-dg return DL

# 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

# count # pairs each distance def dist(m): nr=m.nrows() dist = zero_vector(nr) dist[0]=nr for i in [0..nr-1]: for j in [i+1..nr-1]: d=-m[i,j] dist[d]=dist[d]+1 return dist

################################ # Example 2.1: degree sequence and transmission sequence ################################

g=Graph('FoL^w') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 9 & -1 & -1 & -2 & -2 & -2 & -1 \\ -1 & 9 & -2 & -2 & -2 & -1 & -1 \\ -1 & -2 & 9 & -2 & -1 & -2 & -1 \\ -2 & -2 & -2 & 9 & -1 & -1 & -1 \\ -2 & -2 & -1 & -1 & 8 & -1 & -1 \\ -2 & -1 & -2 & -1 & -1 & 8 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & 6 \end{array}\right)$

h=Graph('F@V~o') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 10 & -2 & -2 & -2 & -2 & -1 & -1 \\ -2 & 9 & -2 & -2 & -1 & -1 & -1 \\ -2 & -2 & 9 & -1 & -2 & -1 & -1 \\ -2 & -2 & -1 & 8 & -1 & -1 & -1 \\ -2 & -1 & -2 & -1 & 8 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & 7 & -2 \\ -1 & -1 & -1 & -1 & -1 & -2 & 7 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x

[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
[12, 10, 9, 7, 0, 8.585786437626905?, 11.414213562373095?]
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x
x^7 - 58*x^6 + 1393*x^5 - 17730*x^4 + 126110*x^3 - 475188*x^2 + 740880*x

print g.degree_sequence() print h.degree_sequence()

[6, 4, 4, 3, 3, 3, 3]
[5, 5, 4, 4, 3, 3, 2]

[6, 4, 4, 3, 3, 3, 3]
[5, 5, 4, 4, 3, 3, 2]

print trs(g) print trs(h)

[6, 8, 8, 9, 9, 9, 9]
[7, 7, 8, 8, 9, 9, 10]

[6, 8, 8, 9, 9, 9, 9]
[7, 7, 8, 8, 9, 9, 10]

################################ # Example 2.2: number edges and girth and distance multiset ################################

g=Graph('HhCWMES') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrr} 14 & -1 & -2 & -2 & -3 & -2 & -2 & -1 & -1 \\ -1 & 15 & -1 & -2 & -3 & -3 & -2 & -1 & -2 \\ -2 & -1 & 15 & -1 & -2 & -2 & -3 & -2 & -2 \\ -2 & -2 & -1 & 13 & -1 & -1 & -2 & -3 & -1 \\ -3 & -3 & -2 & -1 & 17 & -1 & -2 & -3 & -2 \\ -2 & -3 & -2 & -1 & -1 & 13 & -1 & -2 & -1 \\ -2 & -2 & -3 & -2 & -2 & -1 & 15 & -1 & -2 \\ -1 & -1 & -2 & -3 & -3 & -2 & -1 & 15 & -2 \\ -1 & -2 & -2 & -1 & -2 & -1 & -2 & -2 & 13 \end{array}\right)$

h=Graph('HhDGKUO') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrr} 13 & -1 & -2 & -2 & -2 & -2 & -2 & -1 & -1 \\ -1 & 13 & -1 & -2 & -2 & -1 & -2 & -2 & -2 \\ -2 & -1 & 16 & -1 & -2 & -2 & -3 & -3 & -2 \\ -2 & -2 & -1 & 14 & -1 & -2 & -3 & -2 & -1 \\ -2 & -2 & -2 & -1 & 13 & -1 & -2 & -1 & -2 \\ -2 & -1 & -2 & -2 & -1 & 14 & -1 & -2 & -3 \\ -2 & -2 & -3 & -3 & -2 & -1 & 17 & -1 & -3 \\ -1 & -2 & -3 & -2 & -1 & -2 & -1 & 14 & -2 \\ -1 & -2 & -2 & -1 & -2 & -3 & -3 & -2 & 16 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?,
13.50478622306352?, 14.3727299204472?, 16.1088581941218?,
16.8817006711310?, 21.13192499123656?]
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?,
13.50478622306352?, 14.3727299204472?, 16.1088581941218?,
16.8817006711310?, 21.13192499123656?]
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 +
491069091*x^3 - 2237203064*x^2 + 4446151812*x
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 +
491069091*x^3 - 2237203064*x^2 + 4446151812*x

[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?, 13.50478622306352?, 14.3727299204472?, 16.1088581941218?, 16.8817006711310?, 21.13192499123656?]
[0, 13.51071142818992?, 15.71083145355169?, 18.77845711825839?, 13.50478622306352?, 14.3727299204472?, 16.1088581941218?, 16.8817006711310?, 21.13192499123656?]
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 + 491069091*x^3 - 2237203064*x^2 + 4446151812*x
x^9 - 130*x^8 + 7369*x^7 - 237912*x^6 + 4785415*x^5 - 61411718*x^4 + 491069091*x^3 - 2237203064*x^2 + 4446151812*x

print g.num_edges() print h.num_edges()

13
12

13
12

print g.girth() print h.girth()

3
4

3
4

print dist(DL1) print dist(DL2)

(9, 13, 17, 6, 0, 0, 0, 0, 0)
(9, 12, 19, 5, 0, 0, 0, 0, 0)

(9, 13, 17, 6, 0, 0, 0, 0, 0)
(9, 12, 19, 5, 0, 0, 0, 0, 0)

################################ # Figure 2.3: diameter ################################

g=Graph('IzRxzEHHg') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} 14 & -1 & -1 & -2 & -2 & -1 & -2 & -2 & -1 & -2 \\ -1 & 12 & -1 & -1 & -1 & -1 & -2 & -1 & -2 & -2 \\ -1 & -1 & 11 & -1 & -2 & -1 & -1 & -1 & -2 & -1 \\ -2 & -1 & -1 & 15 & -2 & -1 & -1 & -2 & -3 & -2 \\ -2 & -1 & -2 & -2 & 14 & -1 & -1 & -2 & -1 & -2 \\ -1 & -1 & -1 & -1 & -1 & 11 & -1 & -2 & -2 & -1 \\ -2 & -2 & -1 & -1 & -1 & -1 & 12 & -1 & -2 & -1 \\ -2 & -1 & -1 & -2 & -2 & -2 & -1 & 14 & -1 & -2 \\ -1 & -2 & -2 & -3 & -1 & -2 & -2 & -1 & 15 & -1 \\ -2 & -2 & -1 & -2 & -2 & -1 & -1 & -2 & -1 & 14 \end{array}\right)$

h=Graph('I~{KHNgiG') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} 11 & -1 & -1 & -1 & -1 & -2 & -1 & -2 & -1 & -1 \\ -1 & 13 & -1 & -1 & -1 & -2 & -2 & -2 & -1 & -2 \\ -1 & -1 & 11 & -1 & -1 & -2 & -2 & -1 & -1 & -1 \\ -1 & -1 & -1 & 14 & -1 & -2 & -2 & -2 & -2 & -2 \\ -1 & -1 & -1 & -1 & 11 & -1 & -2 & -2 & -1 & -1 \\ -2 & -2 & -2 & -2 & -1 & 15 & -1 & -1 & -2 & -2 \\ -1 & -2 & -2 & -2 & -2 & -1 & 15 & -1 & -2 & -2 \\ -2 & -2 & -1 & -2 & -2 & -1 & -1 & 15 & -2 & -2 \\ -1 & -1 & -1 & -2 & -1 & -2 & -2 & -2 & 13 & -1 \\ -1 & -2 & -1 & -2 & -1 & -2 & -2 & -2 & -1 & 14 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?,
16.41421356237310?, 11.763932022500211?, 11.763932022500211?,
16.23606797749979?, 16.23606797749979?]
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?,
16.41421356237310?, 11.763932022500211?, 11.763932022500211?,
16.23606797749979?, 16.23606797749979?]
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 +
797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 +
797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x

[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?, 16.41421356237310?, 11.763932022500211?, 11.763932022500211?, 16.23606797749979?, 16.23606797749979?]
[15, 0, 12.29843788128358?, 18.70156211871643?, 13.585786437626905?, 16.41421356237310?, 11.763932022500211?, 11.763932022500211?, 16.23606797749979?, 16.23606797749979?]
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 + 797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x
x^10 - 132*x^9 + 7720*x^8 - 262558*x^7 + 5722578*x^6 - 82891102*x^5 + 797942816*x^4 - 4922528058*x^3 + 17658758885*x^2 - 28066657350*x

print g.diameter() print h.diameter()

3
2

3
2

################################ # Figure 2.4: leaf ################################

g=Graph('G@OZN{') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 13 & -2 & -2 & -2 & -2 & -2 & -2 & -1 \\ -2 & 11 & -2 & -2 & -1 & -2 & -1 & -1 \\ -2 & -2 & 11 & -1 & -2 & -2 & -1 & -1 \\ -2 & -2 & -1 & 11 & -2 & -1 & -2 & -1 \\ -2 & -1 & -2 & -2 & 11 & -1 & -2 & -1 \\ -2 & -2 & -2 & -1 & -1 & 10 & -1 & -1 \\ -2 & -1 & -1 & -2 & -2 & -1 & 10 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & 7 \end{array}\right)$

h=Graph('G_C`~{') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 12 & -1 & -2 & -2 & -2 & -2 & -2 & -1 \\ -1 & 12 & -2 & -2 & -2 & -2 & -2 & -1 \\ -2 & -2 & 11 & -2 & -2 & -1 & -1 & -1 \\ -2 & -2 & -2 & 11 & -1 & -2 & -1 & -1 \\ -2 & -2 & -2 & -1 & 11 & -2 & -1 & -1 \\ -2 & -2 & -1 & -2 & -2 & 11 & -1 & -1 \\ -2 & -2 & -1 & -1 & -1 & -1 & 9 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & 7 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[15, 14, 13, 10, 8, 0, 12, 12]
[15, 14, 13, 10, 8, 0, 12, 12]
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 +
19080000*x^2 - 31449600*x
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 +
19080000*x^2 - 31449600*x

[15, 14, 13, 10, 8, 0, 12, 12]
[15, 14, 13, 10, 8, 0, 12, 12]
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 + 19080000*x^2 - 31449600*x
x^8 - 84*x^7 + 3007*x^6 - 59448*x^5 + 700756*x^4 - 4923264*x^3 + 19080000*x^2 - 31449600*x

print g.degree_sequence() print h.degree_sequence()

[7, 4, 4, 3, 3, 3, 3, 1]
[7, 5, 3, 3, 3, 3, 2, 2]

[7, 4, 4, 3, 3, 3, 3, 1]
[7, 5, 3, 3, 3, 3, 2, 2]

################################ # Figure 2.5: dominating vertex ################################

g=Graph('FIefw') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 9 & -2 & -2 & -2 & -1 & -1 & -1 \\ -2 & 9 & -1 & -1 & -2 & -2 & -1 \\ -2 & -1 & 9 & -2 & -2 & -1 & -1 \\ -2 & -1 & -2 & 9 & -1 & -2 & -1 \\ -1 & -2 & -2 & -1 & 9 & -2 & -1 \\ -1 & -2 & -1 & -2 & -2 & 9 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & 6 \end{array}\right)$

h=Graph('F@R~o') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 10 & -2 & -2 & -2 & -2 & -1 & -1 \\ -2 & 9 & -2 & -2 & -1 & -1 & -1 \\ -2 & -2 & 9 & -1 & -2 & -1 & -1 \\ -2 & -2 & -1 & 9 & -2 & -1 & -1 \\ -2 & -1 & -2 & -2 & 9 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & 7 & -2 \\ -1 & -1 & -1 & -1 & -1 & -2 & 7 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[9, 7, 0, 12, 12, 10, 10]
[9, 7, 0, 12, 12, 10, 10]
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x

[9, 7, 0, 12, 12, 10, 10]
[9, 7, 0, 12, 12, 10, 10]
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x
x^7 - 60*x^6 + 1491*x^5 - 19636*x^4 + 144492*x^3 - 563040*x^2 + 907200*x

print g.degree_sequence() print h.degree_sequence()

[6, 3, 3, 3, 3, 3, 3]
[5, 5, 3, 3, 3, 3, 2]

[6, 3, 3, 3, 3, 3, 3]
[5, 5, 3, 3, 3, 3, 2]

################################ # Figure 2.6: cut-vertex ################################

g=Graph('G`Gx}{') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 13 & -1 & -3 & -2 & -2 & -2 & -2 & -1 \\ -1 & 13 & -3 & -2 & -2 & -2 & -2 & -1 \\ -3 & -3 & 12 & -1 & -1 & -1 & -1 & -2 \\ -2 & -2 & -1 & 10 & -2 & -1 & -1 & -1 \\ -2 & -2 & -1 & -2 & 10 & -1 & -1 & -1 \\ -2 & -2 & -1 & -1 & -1 & 9 & -1 & -1 \\ -2 & -2 & -1 & -1 & -1 & -1 & 9 & -1 \\ -1 & -1 & -2 & -1 & -1 & -1 & -1 & 8 \end{array}\right)$

h=Graph('GBXk{{') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 14 & -3 & -3 & -2 & -2 & -2 & -1 & -1 \\ -3 & 12 & -2 & -1 & -1 & -1 & -2 & -2 \\ -3 & -2 & 12 & -1 & -1 & -1 & -2 & -2 \\ -2 & -1 & -1 & 10 & -2 & -2 & -1 & -1 \\ -2 & -1 & -1 & -2 & 9 & -1 & -1 & -1 \\ -2 & -1 & -1 & -2 & -1 & 9 & -1 & -1 \\ -1 & -2 & -2 & -1 & -1 & -1 & 9 & -1 \\ -1 & -2 & -2 & -1 & -1 & -1 & -1 & 9 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 +
18666240*x^2 - 30643200*x
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 +
18666240*x^2 - 30643200*x

[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
[14, 0, 12, 12, 10, 10, 8.87689437438234?, 17.12310562561766?]
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 + 18666240*x^2 - 30643200*x
x^8 - 84*x^7 + 3000*x^6 - 59072*x^5 + 692816*x^4 - 4841152*x^3 + 18666240*x^2 - 30643200*x

print g.vertex_connectivity() print h.vertex_connectivity()

1
2

1
2

################################ # Figure 2.7: symmetry ################################

g=Graph('FJY}o') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 10 & -2 & -2 & -2 & -2 & -1 & -1 \\ -2 & 8 & -1 & -1 & -1 & -2 & -1 \\ -2 & -1 & 8 & -1 & -1 & -1 & -2 \\ -2 & -1 & -1 & 8 & -2 & -1 & -1 \\ -2 & -1 & -1 & -2 & 8 & -1 & -1 \\ -1 & -2 & -1 & -1 & -1 & 8 & -2 \\ -1 & -1 & -2 & -1 & -1 & -2 & 8 \end{array}\right)$

h=Graph('Fbo|w') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 9 & -1 & -2 & -2 & -1 & -2 & -1 \\ -1 & 9 & -2 & -1 & -1 & -2 & -2 \\ -2 & -2 & 9 & -1 & -2 & -1 & -1 \\ -2 & -1 & -1 & 8 & -2 & -1 & -1 \\ -1 & -1 & -2 & -2 & 8 & -1 & -1 \\ -2 & -2 & -1 & -1 & -1 & 8 & -1 \\ -1 & -2 & -1 & -1 & -1 & -1 & 7 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I,
9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I,
9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x

[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I, 9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
[10, 0, 8.381966011250106? + 0.?e-60*I, 10.618033988749894? + 0.?e-60*I, 9.22713444217069?, 12.16424793846022?, 7.608617619369099? + 0.?e-54*I]
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x
x^7 - 58*x^6 + 1395*x^5 - 17810*x^4 + 127301*x^3 - 483016*x^2 + 760060*x

print g.automorphism_group() print h.automorphism_group()

Permutation Group with generators [(3,4), (1,2)(5,6)]
Permutation Group with generators [()]

Permutation Group with generators [(3,4), (1,2)(5,6)]
Permutation Group with generators [()]

################################ # Figure 2.8: planar ################################

g=Graph('G?CR^W') show(g) DL1=distLap(g) show(DL1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 15 & -2 & -2 & -3 & -2 & -2 & -3 & -1 \\ -2 & 13 & -2 & -3 & -2 & -2 & -1 & -1 \\ -2 & -2 & 13 & -3 & -2 & -2 & -1 & -1 \\ -3 & -3 & -3 & 15 & -1 & -1 & -2 & -2 \\ -2 & -2 & -2 & -1 & 11 & -2 & -1 & -1 \\ -2 & -2 & -2 & -1 & -2 & 11 & -1 & -1 \\ -3 & -1 & -1 & -2 & -1 & -1 & 11 & -2 \\ -1 & -1 & -1 & -2 & -1 & -1 & -2 & 9 \end{array}\right)$

h=Graph('G?Kpe[') show(h) DL2=distLap(h) show(DL2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrr} 15 & -2 & -3 & -3 & -2 & -2 & -2 & -1 \\ -2 & 15 & -3 & -3 & -2 & -2 & -2 & -1 \\ -3 & -3 & 13 & -2 & -1 & -1 & -1 & -2 \\ -3 & -3 & -2 & 13 & -1 & -1 & -1 & -2 \\ -2 & -2 & -1 & -1 & 11 & -2 & -2 & -1 \\ -2 & -2 & -1 & -1 & -2 & 11 & -2 & -1 \\ -2 & -2 & -1 & -1 & -2 & -2 & 11 & -1 \\ -1 & -1 & -2 & -2 & -1 & -1 & -1 & 9 \end{array}\right)$

print DL1.eigenvalues() print DL2.eigenvalues() print DL1.charpoly() print DL2.charpoly()

[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?,
18.64776356080690?]
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?,
18.64776356080690?]
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 +
47349497*x^2 - 90671880*x
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 +
47349497*x^2 - 90671880*x

[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?, 18.64776356080690?]
[17, 15, 0, 13, 13, 9.60329164865426?, 11.74894479053886?, 18.64776356080690?]
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 + 47349497*x^2 - 90671880*x
x^8 - 98*x^7 + 4087*x^6 - 94020*x^5 + 1288463*x^4 - 10517842*x^3 + 47349497*x^2 - 90671880*x

print g.is_planar() print h.is_planar()

True
False

True
False

################################ # Lemma 3.8: permutations (14)(23) and (13)(24) are enough ################################

P=Permutations(4).list() L=[] for G in graphs(4): #iterates over all graphs on 4 vertices V=G.vertices() E=G.edges() for p in P: #iterates over all labels of the graph H=Graph(); H.add_vertices(range(4)); for e in E: H.add_edge(p[e[0]]-1,p[e[1]]-1) #Creating the base graph H if (0,1, None) not in H.edges() and (2,3, None) not in H.edges(): #edges we want to add need to not be in graph H1=H.copy(); H1.add_edge(0,1); H2=H.copy(); H2.add_edge(2,3); if H1.is_isomorphic(H2): #Check if isomorphic (hypothesis) J1=H1.copy(); J1.relabel({0:3, 1:2, 2:1, 3:0}); #The possible two permutations J2=H1.copy(); J2.relabel({0:2, 1:3, 2:0, 3:1}); if J1!=H2 and J2!=H2: #If the isomorphism was something else: a counter example L.append([H1, H2, H1.is_isomorphic(H2,certificate=True)[1]]) len(L)

################################ # Theorem 3.9: matrix similarity ################################

a=var('a'); b=var('b'); c=var('c'); d=var('d'); e=var('e'); f=var('f'); h=var('h'); M=matrix([[a+b+c+d, -b, -c, -d], [-b, a+b+f+h, -f, -h], [-c, -f, a+c+f+e, -e], [-d, -h, -e, a+d+h+e]]) show(M)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} a + b + c + d & -b & -c & -d \\ -b & a + b + f + h & -f & -h \\ -c & -f & a + c + e + f & -e \\ -d & -h & -e & a + d + e + h \end{array}\right)$

C1=matrix([[1/2, 1/2, 1/2, -1/2], [1/2,1/2,-1/2,1/2], [1/2, -1/2, 1/2, 1/2], [-1/2, 1/2, 1/2, 1/2]]); show(C1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{array}\right)$

show(C1*M*C1)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} a + d + e + h & -e & -h & -d \\ -e & a + c + e + f & -f & -c \\ -h & -f & a + b + f + h & -b \\ -d & -c & -b & a + b + c + d \end{array}\right)$

C2=matrix([[1/2, 1/2, -1/2, 1/2], [1/2,1/2,1/2,-1/2], [-1/2, 1/2, 1/2, 1/2], [1/2, -1/2, 1/2, 1/2]]); show(C2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \end{array}\right)$

show(C2*M*C2)

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} a + c + e + f & -e & -c & -f \\ -e & a + d + e + h & -d & -h \\ -c & -d & a + b + c + d & -b \\ -f & -h & -b & a + b + f + h \end{array}\right)$

################################ # Example 4.6: eigenvalues of SRG (29,14,6,7) ################################

g=graphs.CirculantGraph(29,[1, 4, 5, 6, 7, 9, 13]) show(g)

DL=distLap(g) DL.eigenvalues()

[0, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I,
46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I]

[0, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 40.80741759643275? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I, 46.19258240356726? + 0.?e-76*I]

nn=29 kk=14 lam=6 mu=7 DLtheta=2*nn-kk+1/2*(lam-mu+sqrt((lam-mu)^2+4*(kk-mu))) DLtau=2*nn-kk+1/2*(lam-mu-sqrt((lam-mu)^2+4*(kk-mu))) mDLtheta=(1/2)*(nn-1-(2*kk+(nn-1)*(lam-mu))/sqrt((lam-mu)^2+4*(kk-mu))) mDLtau=(1/2)*(nn-1-(2*kk+(nn-1)*(lam-mu))/sqrt((lam-mu)^2+4*(kk-mu))) print DLtheta, n(DLtheta), mDLtheta print DLtau, n(DLtau), mDLtau

1/2*sqrt(29) + 87/2 46.1925824035673 14
-1/2*sqrt(29) + 87/2 40.8074175964327 14

1/2*sqrt(29) + 87/2 46.1925824035673 14
-1/2*sqrt(29) + 87/2 40.8074175964327 14

BDGLRSY18-Distance_Laplacian

1429 days ago by hogben