[SOLVED] CPTS553- Graph Theory: Assignment 8

Description

There’s only one question, with four parts.

Let 𝐺 be a graph having Laplacian matrix

Recall that the eigenvalues of 𝐿 will take the form

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

1

1

1

¹

𝐯₁ =  ¹1  ;  𝜆₁ = 0.

1

1

1

[1]

3. Use a matrix calculator to find 𝜆₂ and 𝜆₃ together with eigenvectors 𝐯₂ and 𝐯₃. You’re on the right track if your values of 𝜆₂ and 𝜆₃ are about 875 and 1, respectively.  Also, check that the entries of 𝐯₂ and 𝐯₃ sum to 0 (this

is a consequence of the eigenvectors corresponding to different eigenvalues of 𝐿 being orthogonal.)

1. Let

1

𝐱                            and 𝐲 = 𝐯 ;

these vectors 𝐱 and 𝐲 are unit vectors.

Letting 𝑥_𝑖 and 𝑦_𝑖 be the 𝑖^𝑡ℎ coordinates of 𝐱 and 𝐲, respectively, plot the points

(𝑥₁,𝑦₁),(𝑥₂,𝑦₂),…,(𝑥₁₀,𝑦₁₀)

in ℝ² 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.

10. Do the same process in part A to find 𝜆₉ and 𝜆₁₀ along with corresponding eigenvectors 𝐯₉ and 𝐯₁₀. You should expect 𝜆₉ and 𝜆₁₀ to be about 5 and 5.76, respectively.

1. 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?