403 – HW 4 – Algebraic graph theory

April 28, 2014

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.