CPTS 553: Graph Theory Assignment 8 solved

Description

1. Let 𝐺 have Laplacian matrix
𝐿 =
[

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

A. Use a matrix calculator to find the eigenvalues of 𝐿; there should be
some pairs of them that have the same value. List them in order
0 ≤ 𝜆2 ≤ 𝜆3 ≤ 𝜆4 ≤ 𝜆5 ≤ 𝜆6 ≤ 𝜆7
.
It’s fine (suggested, actually) that you use decimal approximations
rather than exact values.
B. Use a matrix calculator to find eigenvectors 𝐯 and 𝐰 corresponding to
𝜆2 and 𝜆3
. It’s fine if you use decimal approximations for these.
Compute the vector
𝐳 = 𝐰 −
𝐯 ⋅ 𝐰
𝐯 ⋅ 𝐯
𝐯.
This vector 𝐳 is orthogonal to 𝐯.
C. Let 𝐱 =
1
√𝐯⋅𝐯
𝐯 and 𝐲 =
1
√𝐳⋅𝐳
𝐳 and plot the points
(𝑥1
, 𝑦1
), (𝑥2
, 𝑦2
), (𝑥3
, 𝑦3
), (𝑥4
, 𝑦4
), (𝑥5
, 𝑦5
), (𝑥6
, 𝑦6
), (𝑥7
, 𝑦7
)
and for each edge 𝑖𝑗 of 𝐺, draw the segment joining (𝑥𝑖
, 𝑦𝑖
) to
(𝑥𝑗
, 𝑦𝑗
).
The result in C should be a “nice” drawing of 𝐺, in the sense that
adjacent vertices are close together.
D. Do the same process in parts B and C for the eigenvectors
corresponding to 𝜆6 and 𝜆7
, the two largest eigenvalues.
E. The end result in part D should cause adjacent vertices to be drawn far
apart and give you an idea of how to assign colors to the vertices to
determine the chromatic number of 𝐺. What is this chromatic
number?
2. Consider the tournament whose adjacency matrix is
𝑇 =
[

0 1 1 1 1 0 0
0 0 1 1 1 0 1
0 0 0 1 1 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 1
1 1 1 1 0 0 1
1 0 1 1 0 0 0]

Here, 𝑇𝑖𝑗 = 1 if player 𝑖 defeated player 𝑗 in the tournament.
A. Use software of your choice to compute 𝑇
2
, 𝑇
4
, 𝑇
8
, 𝑇
16 – this is
most easily accomplished by squaring the matrix successively,
rather than by computing the powers individually.
B. As you successively square the matrix, the columns should begin to
converge to multiples of each other. What’s happening is that the
columns are converging to multiples of the dominant eigenvector.
C. According to the relative values of column entries, how should the
participants be ranked?
D. In part C, did you find that any player who won fewer games was
more highly ranked than someone who won more games?