Assignment 3-
1. Determine the spectrum of the following graphs. For this problem, it may be useful to consider the following. The adjacency matrix A(G) of a graph G on n vertices can be identified as a linear map from Rn to Rn. If v ∈ Rn is an eigenvector of A(G) with eigenvalue λ, then
[A(G)v]i = ∑jvj,
and hence
λvi = ∑jvj
where j runs through all vertices adjacent to i. In other words, we can construct an eigenvector with eigenvalue λ by putting weights vi on each vertex i in a graph, in such a way that the sum of the weights of the neighbors of a given vertex is always λ times the weight of that vertex. This will be helpful for some or all parts of this problem.
(a) Km,n, the complete bipartite graph with bipartition (A, B) where |A| = m and |B| = n.
(b) Cn, the cycle on n vertices.
(c) The Petersen graph below. Do this without the aid of a computer, and without calculating a large determinant.
2. Recall the Laplacian of any graph G is the matrix L(G) whose rows and columns are indexed by the same ordering of V (G), and with L(G)ij = deg(i) if i = j, -1 if ij ∈ E(G), and 0 otherwise.
(a) Show that 0 is always an eigenvalue of L(G).
(b) Show that if G is regular with degree k, then the largest eigenvalue of L(G) is k.
(c) Let σ be an arbitrary orientation of the edges of a graph G. The incidence matrix Dσ(G) with respect to the orientation σ is the matrix whose rows are indexed by V (G) and columns indexed by E(G), with ij-entry equal to 1 if vertex i is the head of the directed edge j, and -1 if it is the tail. Show that for any orientation σ, L(G) = Dσ(G)Dσ(G)T.
(d) Using part (c), show that if 0 is an eigenvalue of L(G) with multiplicity k, then G has k distinct connected components. (Hint: Start by showing that Dσ(G) and Dσ(G)Dσ(G)T have the same rank for any orientation σ of the edges, then compute the rank of Dσ(G)).
3. Let G be a connected graph. Let λmax(G) be the largest eigenvalue of A(G). In class we proved a lower bound for χ(G) in terms of spectra. In this problem we will prove an upper bound.
(a) For any graph H, let δ(H) be the minimum degree of a vertex in H. Show that δ(H) ≤ λmax(H).
(b) Show that if H is any induced subgraph of G, then λmax(H) ≤ λmax(G).
(c) Show that G has an induced subgraph with minimum degree at least χ(G) - 1, and conclude the result.
4. (a) Show that the number of labeled trees on n vertices is nn-2.
(b) Let G be the graph of the n-dimensional hypercube. That is, V (G) is the set of n-bit binary strings, with two strings u, v adjacent if and only if they differ in exactly one bit. Determine the number of spanning trees in G.
5. We determined an upper bound for the number of vertices in a d-regular graph with diameter k. Consider such a graph with k = 2. By the first assignment,
|V (G)| ≤ 1 + d + d(d - 1) = d2 + 1.
In this problem we will prove that, if |V (G)| = d2 + 1, then d = 2, 3, 7 or 57. It is still an open problem to construct an example when d = 57.
(a) Show that if a graph G is d-regular with diameter 2, and |V (G)| = d2 + 1, then G has girth 5.
(b) Show that G is strongly regular with parameters (d2 + 1, d, 0, 1).
(c) Show that one of the following two must be true:
- d = 2
- 4d - 3 is a square.
(d) Suppose the second holds. Let s be a positive integer such that s2 = 4d - 3. Show that one of the multiplicities of one of the eigenvectors of the adjacency matrix of G, call it m, satisfies s5 + s4 + 6s3 - 2s2 + (9 - 32m)s - 15 = 0, and deduce s ∈ {1, 3, 5, 15}.
(e) Deduce, using all the above parts, that d = 2, 3, 7 or 57.