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$.