403 – HW 4 – Algebraic graph theory

This set is due Thursday, May 15, at 11am.

1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let \Gamma be a (finite, simple) graph with n vertices, and let A be its adjacency matrix. Suppose that the characteristic polynomial of A is {\rm char}_A(x)=x^n+c_1x^{n-1}+c_2x^{n-2}+\dots+c_n. Verify that:

  1. c_1=0.
  2. -c_2 is the number of edges in \Gamma.
  3. -c_3 is twice the number of triangles in \Gamma.

2.  (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let G be a finite simple graph on n vertices that is k-regular, that is, such that each vertex has degree k. Suppose G has n vertices and A is its adjacency matrix.

  1. Verify that k is an eigenvalue of A.
  2. Let \lambda_2,\dots,\lambda_n be the other eigenvalues of A. Let \bar G denote the complementary graph to G: This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in G. Let B be the adjacency matrix of \bar G. Show that there is a basis of \mathbb R^n consisting of vectors that are common eigenvectors of B and A, and that the eigenvalues of B are n-k-1,-1-\lambda_2,\dots,-1-\lambda_n.

3 Responses to 403 – HW 4 – Algebraic graph theory

  1. […] 1. Matoušek’s lecture 21 (continued). Algebraic graph theory. Homework 4, due May […]

  2. I’ve slightly changed the phrasing of question 2: Rather than asking to show that A and B 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 G on vertex set \{1,2,3,4\} and only two edges: 1 connected to 2, and 3 connected to 4. The vector \left(\begin{array}{c}1\\1\\{0}\\{0}\end{array}\right) is an eigenvector of A, but not of B.

    • As an extra credit problem (to be turned in with the rest of the homework), check that if G and \bar G are both connected, then we can recover the stronger conclusion: A and B have exactly the same eigenvectors.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: