1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let be a (finite, simple) graph with vertices, and let be its adjacency matrix. Suppose that the characteristic polynomial of is . Verify that:
.
is the number of edges in .
is twice the number of triangles in .
2. (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let be a finite simple graph on vertices that is -regular, that is, such that each vertex has degree . Suppose has vertices and is its adjacency matrix.
Verify that is an eigenvalue of .
Let be the other eigenvalues of . Let denote the complementary graph to : This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in . Let be the adjacency matrix of . Show that there is a basis of consisting of vectors that are common eigenvectors of and , and that the eigenvalues of are .
This entry was posted on Monday, April 28th, 2014 at 9:35 pm and is filed under 403/503: Linear Algebra II. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
3 Responses to 403 – HW 4 – Algebraic graph theory
I’ve slightly changed the phrasing of question 2: Rather than asking to show that and have the same eigenvectors, I am now asking the weaker result that there is a basis consisting of common eigenvectors. The result as stated originally (which is how it is stated in the Godsil-Royle book) is false:
Consider the graph on vertex set and only two edges: connected to , and connected to . The vector is an eigenvector of , but not of .
As an extra credit problem (to be turned in with the rest of the homework), check that if and are both connected, then we can recover the stronger conclusion: and have exactly the same eigenvectors.
.
is the number of edges in
is twice the number of triangles in
be the other eigenvalues of
denote the complementary graph to
be the adjacency matrix of
consisting of vectors that are common eigenvectors of
.
A kind of library 
[…] 1. Matoušek’s lecture 21 (continued). Algebraic graph theory. Homework 4, due May […]
I’ve slightly changed the phrasing of question 2: Rather than asking to show that
and 
have the same eigenvectors, I am now asking the weaker result that there is a basis consisting of common eigenvectors. The result as stated originally (which is how it is stated in the Godsil-Royle book) is false:
Consider the graph
on vertex set 
and only two edges: 
connected to 
, and 
connected to 
. The vector 
is an eigenvector of 
, but not of 
.
As an extra credit problem (to be turned in with the rest of the homework), check that if
and 
are both connected, then we can recover the stronger conclusion: 
and 
have exactly the same eigenvectors.