There’s only one question, with four parts.
Let πΊ be a graph having Laplacian matrix
3
−1
−1
−1
πΏ = 0
0
0
0
0
[ 0
−1
3
0
−1
−1
0
0
0
0
0
−1
0
2
0
0
0
0
−1
0
0
−1
−1
0
4
−1
−1
0
0
0
0
0
−1 0
−1
3
0
−1
0
0
0
0
0
0
−1
0
4
0
−1
−1
−1
0
0
0
0
−1
0
2
0
0
−1
0
0
−1
0
0
−1
0
3
−1
0
0
0
0
0
0
−1 0
−1 3
−1
0
0 0
0
0
−1 −1
0
−1
3 ]
Recall that the eigenvalues of πΏ will take the form
We will associate with each eigenvalue ππ its corresponding eigenvector π―π. For instance,
1
1
1
1
π―1 = 11 ; π1 = 0.
1
1
1
[1]
A. Use a matrix calculator to find π2 and π3 together with eigenvectors π―2 and π―3. You’re on the right track if your values of π2 and π3 are about 0.875 and 1, respectively. Also, check that the entries of π―2 and π―3 sum to 0 (this
is a consequence of the eigenvectors corresponding to different eigenvalues of πΏ being orthogonal.)
B. Let
1
π± and π² = π― ;
these vectors π± and π² are unit vectors.
Letting π₯π and π¦π be the ππ‘β coordinates of π± and π², respectively, plot the points
(π₯1,π¦1),(π₯2,π¦2),…,(π₯10,π¦10)
in β2 and for each edge ππ of πΊ, draw the segment joining (π₯π,π¦π) to
(π₯π,π¦π).
The result should be a “nice” drawing of πΊ in the sense that adjacent vertices are drawn close together.
C. Do the same process in part A to find π9 and π10 along with corresponding eigenvectors π―9 and π―10. You should expect π9 and π10 to be about 5 and 5.76, respectively.
D. Repeat the process in part B where
1 1
π± = π― and π² = π― .
This time, the resulting drawing should have adjacent vertices drawn far apart and so vertices that are drawn close together could be assigned the same color in a graph coloring. This should give you an indication of the chromatic number of πΊ. What is this number?
