Math 581: Topics in Graph Theory: Algebraic Graph Theory
Fall 2006

Additional Exercises

To the main course page.

• Ch. 1, #A1: Let A be the adjacency matrix of a graph X. Let f be any permutation of V (not necessarily an automorphism of X) and let P be its matrix. Let Y = f(X), that is, the graph resulting by applying f to X. Show that A(Y) = P^-1AP, or PAP, or something like that (you have to find out what; I guarantee there is a correct answer).
• Ch. 1, #A2: Prove that, if there is a walk in X from u to v, then there is a path from u to v.

---

• Ch. 2, #A1: Prove that the action of Sym(V) on P^(k)(V) (the class of k-element subsets of V) is transitive.
• Ch. 2, #A2: Decide whether or not the only subgroup of Sym(V) with the property of #A1 is Sym(V) itself. If not, can you find all subgroups with this property?
• Ch. 2, #A3: Complete the missing step in the proof of Lemma 2.5.1, that B = x^H is smaller than V.

---

• Ch. 3, #A1: Is {000, 011, 101, 110} a block of imprimitivity of Q₃?
• Ch. 3, #A2: The hyperoctahedral group O_n is the subgroup of Aut Q_n that is generated by Sym(n) acting on the coordinate positions and the bijections τ_i (i = 1,...,n) that reverse the value in the i-th coordinate.
  1. Show that |O_n| = 2ⁿn!.
  2. Show that Aut Q_n = O_n.
• Ch. 3, #A3: Take the "root" vertex in Q_n to be 0ⁿ.
1. Show that the distance dist(0ⁿ, v) is maximized by 1ⁿ and no other vertex. What is the analogous statement if 0ⁿ is replaced by some other vertex?
2. Show that {0ⁿ, 1ⁿ} is a block of imprimitivity of Aut Q_n.
3. Can you find another block of imprimitivity?

---

• Ch. 4, #A1: What additional hypothesis is needed to make it true that s-arc transitivity implies (s−1)-arc transitivity? Is it sufficient to assume transitivity?
• Ch. 4, #A2: We would like to say that in X^(s), the s-arc digraph of X, there is a directed edge AA' if and only if A and A' are s-arcs such that head(A) = tail(A'). Find a counterexample, and decide what hypothesis needs to be added to make this a true statement.
• Ch. 4, #A3: If X is s-arc transitive, then X^(s) is transitive. Is the converse true?
• Ch. 4, #A4: Suppose we leave out of the definition of a distance-transitive graph the requirement that it be connected. What additional examples are there? Can you classify them all?
• Ch. 4, #A5: Find all distance-transitive graphs X with diameter d = 2, such that the complement X^c is disconnected. (I think there are not many of them. We proved that the complement is distance transitive if it is connected, so this problem is to find the bad guys, that fail to have connected complement.)
• Ch. 4, #A6: Find the valency of the i-distance graph J(n,d)_(i) — which, as we saw, equals the generalized Johnson graph J(n,d,d−i). (You should make sure you know how to verify that fact, too.)
• Ch. 4, #A7: Let A = A(X), the adjacency matrix of X. Prove that the (i,j) entry of A^r is the number of walks in X of length r from v_i to v_j. (This question really belongs in Ch. 8 but it's valuable now for the study of distance regular graphs.)
• Ch. 4, #A8: A regular graph X of order n has valency k and finite diameter d > 1.
  1. Recall (or calculate) n₀, the maximum possible number of vertices of X. Assume k > 2 in this part.
  2. Classify all extremal graphs, that is, graphs X whose order equals n₀; or if you can't classify them all, find out as much as you can about them and their structure. Assume k > 1 in this part.
  3. Are all extremal graphs distance regular? You may not have to solve (b) to solve this (I'm not saying). Again, assume k > 1 in this part.
• Ch. 4, #A9: The general theory says that, if X is distance regular with diameter d, then A₃ = A(X₃) is a cubic polynomial function of A = A(X). Find this polynomial explicitly.
• Ch. 4, #A10: Extend the result of Problem #A6 by finding the intersection numbers of the Johnson graph J(n,k). (These are the numbers a_i, b_i, and c_i.)
• Ch. 4, #A11: Prove Theorem 3 of distance regular graphs: A_iA_j = Sum_m=0,1,...,d p^m_ij A_m, where p^m_ij = the number of vertices at distance i from u and distance j from v, if u and v are vertices such that d(u,v) = m.
• Ch. 4, #A12: Show that K_n and K_r,r are distance transitive and find their intersection arrays.

---

• Ch. 5, #A1: The original definition of a Moore graph.
  1. Prove that a graph with maximum valency at most k and with diameter d has at most
     n(k,d) := 1 + k + k(k−1) + ... + k(k−1)^d−1
     vertices.
  2. Let's call a graph with maximum valency at most k, diameter d, and exactly n(k,d) vertices an original Moore graph. Prove that an original Moore graph is k-regular and has girth g = 2d + 1. (That is, it's a Moore graph as defined in the book.)
  3. Prove that a k-regular graph with diameter d and girth 2d + 1 is an original Moore graph. (In other words, we could have defined a Moore graph to be what I'm calling an "original Moore graph"; in fact, that was the original definition of a Moore graph. Maybe people use the girth definition because it's easier to state.)

---

• Ch. 8, #A1: Prove that, if M is any matrix, the rank of MM^T equals that of M.
• Ch. 8, #A2: Prove that, if A is the adjacency matrix of X, Δ is its degree matrix, and D is an oriented incidence matrix of X, then DD^T = Δ − A.
• Ch. 8, #A3: Assume X is k-regular. Under what conditions is −k an eigenvalue of X?
• Ch. 8, #A4: For a graph X, we computed DD^T, BB^T, and B^TB. Is there anything interesting about D^TD?
• Ch. 8, #A5: Find an intrinsic characterization of antibalanced signed graphs. (I mean, not in terms of the negative of Σ.)
• Ch. 8, #A6: Characterize all contrabalanced signed graphs. (Do your best.)
• Ch. 8, #A7: For a signed graph Σ, D(Σ) is an oriented incidence matrix, A(Σ) is the adjacency matrix, and Δ(||Σ||) is the degree matrix of the underlying graph. Verify that DD^T = Δ − A. (Verify that this generalizes #A2.) Preferably, don't assume ||Σ|| is simple, but do assume there are no loops.
• Ch. 8, #A8: Prove that switching acts as a group on signed graphs. I mean: if η, η' : V —> {+,−}, then (Σ^η)^η' = Σ^ηη'.
• Ch. 8, #A9: Prove Lemma 1: Let F be a forest in a signed graph Σ. Then there is a switching of Σ in which F is all positive.
• Ch. 8, #A10: Prove Lemma 2: Suppose a graph has two signings that are switching equivalent. Then the two signings agree on a maximal forest if and only if they agree everywhere.
• Ch. 8, #A11: Write a complete, correct, and clear proof (a CCC proof) of Lemma 3: A signed graph is balanced iff it switches to all positive signs. Also, write a CCC proof of Harary's Bipartition Theorem; use Lemma 3. (This means: clean up the proof I gave in class.)
• Ch. 8, #A12: The frustration index, l(Σ), of a signed graph Σ, written l(Σ), is the smallest number of edges whose deletion makes the graph balanced. E.g., if Σ is balanced, the frustration index is 0. Prove that the frustration index is equal to the smallest number of negative edges in any switching of Σ. (Finding the frustration index is an important and difficult problem in general.)
• Ch. 8, #A13: Take a connected, all-negative signed graph (Γ,−). Find a spanning tree T. Find a switching function η such that switching by η makes T all positive. How many negative edges are left? Try another spanning tree and answer the same question. Do this for some of the following graphs:
  1. Γ = K₃
  2. Γ = K₄
  3. Γ = K₅
  4. Γ = P, the Petersen graph
• Ch. 8, #A14:
  1. In the preceding question, for each graph, what is the smallest number of negative edges, over all spanning trees?
  2. In general, what is the relationship between the smallest number of negative edges over all spanning trees, and the frustration index?
• Ch. 8, #A15: Prove that Δ(||Σ||) + A(Σ) is positive definite. What is its rank, in terms of properties of Σ?
• Ch. 8, #A16: Suppose the underlying graph ||Σ|| is k-regular. Prove all eigenvalues are in the interval [−k,k] and find the multiplicities of k and -k as eigenvalues. (Multiplicity 0 means the number is not an eigenvalue.)
• Ch. 8, #A17: We know that the unoriented incidence matrix B(X) and the oriented incidence matrix D(X) of a graph usually differ significantly, e.g., they have different ranks. Explain this in terms of signed graphs, and find all the graphs for which the two matrices have the same rank. Now, find all the signed graphs for which D(Σ) and D(−Σ) have the same rank. How are Σ and −Σ related in these signed graphs, and does that relationship characterize such signed graphs? (It may be most interesting to answer the question for connected graphs.)
• Ch. 8, #A18: Fill in the details of p. 172, line 4 ("we find the n eigenvalues of C_n."). Your work should include the multiplicities and eigenvectors. (This is a significant amount of work, but not an unreasonable amount.)
• Ch. 8, #A19: Re p. 172, line 5: Look into circulant graphs. Hint: Begin with an easy one, say, X(Z_n,{+1, −1, +2, −2}). See whether your conclusions generalize to all circulant graphs.
• Ch. 8, #A20: What can you find out about the eigenvalues of the path P_n of length n − 1? Hints: Try to find the characteristic polynomial. Begin with small cases. (This is closely related to Exercise 8.11 in the book.)
• Ch. 8, #A21: Show directly in the graph, without algebra, that the local complementation operators of a graph satisfy the identities
    σ_uσ_v = σ_vσ_u if u and v are distinct nonadjacent vertices, and
    σ_uσ_vσ_u = σ_vσ_uσ_v if u and v are adjacent.
• Ch. 8, #A22: Let V = {1,2,...,n} and let Graph_V be the set of all graphs with vertex set V. Let C be the group of local complementation operators σ_i, i in V, acting on Graph_V. Finally, let G be the group with presentation
    <σ₁,...,σ_n: σ_i²=1, σ_iσ_j=σ_jσ_i if i and j are distinct and not adjacent,
            σ_iσ_jσ_i=σ_jσ_iσ_j if i and j are adjacent >
  We know A is a homomorphic image of G. Is A equal to G? (Research question, but it might be interesting to look at small values of n.)
• Ch. 8, #A23: The adjacency matrix A(Σ) of a signed graph is not ≥ O, the zero matrix, but if we form A(hat)(Σ) := A(Σ) + J − I, then A(hat) is nonnegative so one can apply the Perron-Frobenius theorem. How are the eigenvectors of A and A(hat) related? How are the eigenvalues related? Can you get any interesting information about the eigenvalues of A, or about Σ itself, from the Perron-Frobenius theorem applied to A(hat)? Another question: is A(hat) positive semidefinite? (Research questions. The last one may be easy.)

---

• Ch. 10, #A1: If X is a graph such that some quadratic polynomial in A is equal to a multiple of J (the all-1's matrix), then X is strongly regular. (This is the converse of a fact about strongly regular graphs that generalizes to distance regular graphs.)
• Ch. 10, #A2: Suppose M is a symmetric matrix of rank 1, and has eigenvector u associated with its unique nonzero eigenvalue r. Prove that M is a multiple of uu^T and find the multiplier.
• Ch. 10, #A3: Try to obtain further information about the parameters of a strongly regular graph if we require that Δ be a perfect square (as is the case in one of the two types of strongly regular graph).
• Ch. 10, #A4: Prove the Paley graph is strongly regular. (Note that this exercise is implicit in the fact that the text tells you it is but without giving a proof.)
• Ch. 10, #A5: Do the hand computations at the beginning of Section 10.5.
• Ch. 10, #A6: How far can you get towards a characterization or classification of conference graphs? This means (a) extracting from the equations as much information as possible about the allowed parameters, (b) checking to see which parameter sets you know exist, based on examples in the book (or find new ones and get a research paper!), and (c) disproving the existence of some small ones. In particular, give a simpler proof of Lemma 10.3.2 by using the expression 2k + (n−1)(a−c) that is the numerator over the square root of Δ in the multiplicity formulas.
• Ch. 10, #A7: Construct the Paley graphs P(q) for q = 5, 9.
• Ch. 10, #A8: Suppose G is a rank 3 permutation group, such that its orbits on G×G are symmetric. Show that either one of the nondiagonal orbits makes a strongly regular graph.
• Ch. 10, #A9: Show that, if X is a connected s.r.g. with disconnected complement, then k − τ < n. (This is needed in proving the improved version of Lemma 10.3.5.)
• Ch. 10, #A10: If C is a conference matrix in standard form (no negatives in row 1 or column 1), let S be the matrix obtained by deleting row and column 1. Conversely, if M is a square matrix, construct M' by putting a row of 1's above M, a column of 1's on its left, and a 0 at the top left position. Finally, if X is a graph, let S(X) denote its Seidel matrix, or (−1,1,0)-adjacency matrix. Prove: Theorem. If C is a symmetric conference matrix, then S is the Seidel matrix of a conference graph, and conversely, if X is a conference graph, then S(X)' is a symmetric conference matrix.
• Ch. 10, #A11: Lemma 10.8.1 says that a generalized quadrangle of order (s,t) (I will call this a GQ(s,t)) determines a strongly regular graph with parameters ( (s+1)(st+1), s(t+1), s−1, t+1 ) (I will call this an SRG[s,t] to save on the notation). The question is whether this determination is reversible. That is, given an SRG[s,t], is it the point graph of a unique GQ, which is necessarily a GQ(s,t)? An affirmative answer would clarify the idea in the proof of Corollary 10.9.5. This problem should be easy, at least when s = 2, which is the case we want in the corollary.
• Ch. 10, #A12: I'll write c X for the complement of a graph X (due to HTML limitations).
  Verify that A(c L(K₈)) has the eigenvalues 15 (multiplicity 1), 1 (mult. 7), and −5 (mult. 20).
  Deduce from this that S(c L(K₈)) has the two distinct eigenvalues 9 (mult. 7) and −3 (mult. 21).
• Ch. 10, #A13 (new): Find the strongly regular graphs with only two eigenvalues.

  ---

• Ch. 11, #A1: What is the relationship between switching of signed graphs and switching of graphs (i.e., between signed graph switching and graph switching)? Write out a proof of the bijections between two-graphs on vertex set V, switching classes of signed complete graphs on V, and switching classes of graphs on V.
• Ch. 11, #A2: Let S = S(X) = A(K_X), i.e., the Seidel matrix of a graph X. Prove that S has at least two eigenvalues (this means distinct eigenvalues) and, if it has only two eigenvalues, then its corresponding set of equiangular lines meets the relative bound.
• Ch. 11, #A3A (new): Prove that the antipodal mapping ˜α of the double covering graph of a signed graph is an automorphism of the double cover. (By the double covering graph I mean (˜Σ, ˜α), that is, the graph, ˜Σ, together with its antipodality, ˜α.)
• Ch. 11, #A3: Axiomatize the definition of the double covering graph of a signed complete graph. (By the double covering graph I mean (˜Σ, ˜α), that is, the graph, ˜Σ, together with its antipodality, ˜α.)
• Ch. 11, #A4: Generalize #A4 to all signed simple graphs.
• Ch. 11, #A5: Suppose T is a regular two-graph of order n (i.e., on n vertices). Let t be the number of triples of T that lie on each pair of vertices. Calculate the two eigenvalues of the Seidel matrix S(T), as follows: Write down the quadratic equation satisfied by an eigenvalue ρ of S(T) in terms of n and t. Solve for the eigenvalues ρ₁ > ρ₂. Show that the eigenvalues are integers if T is not trivial, and evaluate them in an expression that is a sum and difference of integers; for this you need to introduce one additional integral parameter, call it m, which appears naturally due to the integrality of the eigenvalues. (Part of the problem is to find out what m is.) Use our work on eigenvalues of strongly regular graphs as a guide. For a best solution, find restrictions on m.
• Ch. 11, #A6: Let A be the adjacency matrix of a signed graph. Show that a power B = A^r (r ≥ 0) has entries b_ij equal to the number of positive walks from v_i to v_j of length r, less the number of negative walks.
• Ch. 11, #A7: FALSE! (thanks, Jackie). Suppose X is a k-regular graph, U is a subset of the vertex set, and the switched graph X^U is j-regular. Prove that j = k.
• Ch. 11, #A8: Write V = V(K_n) and E = E(K_n). Let X = L(K_n), so V(X) = E. Suppose U is a subset of V(X) (i.e., of E) such that X^U is regular. Prove that U, as a spanning subgraph of K_n, is regular. ("Spanning subgraph" means that U has vertex set V = V(K_n), i.e., it is treated as the graph (V,U).) Note that there might be exceptions for small values of n; finding exceptions is part of the question. (That's combinatorics!)
• Ch. 11, #A9: Prove that the least eigenvalue of each Chang graph is −2. Can you find the entire spectrum of the Chang graphs and of K₈?
• Ch. 11, #A10: This problem is about strong regularity of the Chang graphs.
  1. Find their parameters (n, k, a, c).
  2. Are they and L(K₈) the only SRG(28, 12, a, c) (a and c being allowed to vary)?
• Ch. 11, #A11: Let's extend Ch. 11 Exercise 7 by asking for all the switchings of the Petersen graph P that give its complement. That is, find all vertex subsets U such that P^U is the complement.

---

• Ch. 12, #A1: Define a sign-biased graph to be a pair (Γ, B) such that B is the class of positive circuits in some signing of Γ. Prove Theorem SB. A pair (Γ, B) where B is a class of circuits of Γ is a sign-biased graph if and only if B consists of all circuits that lie in some subspace of the binary cycle space of Γ. (The binary cycle space can be regarded as the class of subsets of E that have even degree at every vertex.)
• Ch. 12, #A2: This duplicates Ch. 8, #A7. (Thanks, Elizabeth.) Prove that, with our definition of the line graph Λ(B) of a bidirected graph B, the formula D(B)^T D(B) = Δ - A(B) holds.
• Ch. 12, #A3: Prove that a generalized line graph L(Γ, m) has least eigenvalue −2 (or greater), by the following method: Compare the incidence matrix of −Γ to that of Σ = −Γ with the requisite numbers of negative digons added. Use this to compare the adjacency matrix of L(Γ) to that of L(Γ, m). From your comparison, you should be able to dedude the eigenvalue bound.
  I think this comparison will also be interesting in itself. For instance, you can compare the ranks.
• Ch. 12, #A4: Suppose you have a simply signed graph, Σ. Is its line graph simply signed? How about the reduced line graph? The same questions, if Σ is a reduced signed graph.
• Ch. 12, #A5: Suppose you have an all-negative signed graph. Prove it is balanced if and only if the graph is bipartite. (Consequence: Balance is a generalization of biparticity.)
• Ch. 12, #A6: Prove that a signed graph is antibalanced iff it switches to all negative.
• Ch. 12, #A7: Produce a finite system of vectors in some Rⁿ that satisfies (a) and (b) of the definition of a root system on page 268 but not (c) in the errata.
• Ch. 12, #A8: Consider a signed graph Σ with eigenvalues ≤ 2, and its associated line system L. Prove that L is indecomposable if and only if Σ is connected and not equal to ±K₂.

To the main course page.

To my home page.