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.

[…] 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.