CPTS553 Assignment 8 Solved

There’s only one question, with four parts. Let 𝐺 be a graph having Laplacian matrix

3 −1 −1 −1 0

−1 3 −1 0 −1 −1

0 −1 0 0 0 0 0 0 0 0

[0 0

0 2 0 0 0 0

−1 −1
0 0
4 −1 −1 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 −1

0 −1 0 2 0 0 −1 −1 0 0 −1 0 3 −1 0

0 0 0 −1 0 −1 3 −1 0 0 0 −1 −1 0 −1 3]

Recall that the eigenvalues of 𝐿 will take the form
0=𝜆1 ≤𝜆2 ≤𝜆3 ≤𝜆4 ≤𝜆5 ≤𝜆6 ≤𝜆7 ≤𝜆8 ≤𝜆9 ≤𝜆10

We will associate with each eigenvalue 𝜆𝑖 its corresponding eigenvector 𝐯𝑖. For instance,

1 1 1 1

𝐯 = 1 ; 𝜆 = 0. 111

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.)

2. Let

   𝐱 = 1 𝐯2 and 𝐲 = 1 𝐯3; √𝐯2 ⋅𝐯2 √𝐯3 ⋅𝐯3

   these vectors 𝐱 and 𝐲 are unit vectors.
   Letting 𝑥𝑖 and 𝑦𝑖 be the 𝑖𝑡h coordinates of 𝐱 and 𝐲, respectively, plot the

   points

   (𝑥1, 𝑦1), (𝑥2, 𝑦2), … , (𝑥10, 𝑦10)
   in R2 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.

3. Do the same process in part A to find 𝜆9 and 𝜆10 along with corresponding eigenvectors 𝐯 and 𝐯 . You should expect 𝜆 and 𝜆 to be about 5 and

910 910

5.76, respectively.
D. Repeat the process in part B where

𝐱= 1 𝐯and𝐲= 1 𝐯.

√𝐯⋅𝐯 9 √𝐯 ⋅𝐯 10 9 9 10 10

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?