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

Errata and additions for the textbook

To the main course page.

Here is a link to the authors' errata page.

Here are additional errata of my own (with a little help from my students) and some supplementary definitions, etc.:

• P. 1, missing definition: Two edges are "incident" if they have a vertex in common. (A more usual name is "adjacent".)
• P. 3: The authors' definition of induced subgraph is valid only for simple graphs. The explanation in terms of deleting vertices is valid for all graphs.
• P. 3: A clique is sometimes defined as a set of mutually adjacent vertices (thus, it is a subset of V), and sometimes as a complete subgraph (thus, it is a graph). The latter is given by the authors, but they also think in the former way; in particular, what they mean by "size" is the number of vertices, as if a clique is a vertex set.
• P. 9, definition of generalized Johnson graphs: v, k, and i are nonnegative; they don't have to be positive.
• P. 9, Lemma 1.6.1: Add the hypothesis that v - 2k + i ≥ 0. If this is not true, the alleged isomorphism is meaningless because the second graph is undefined.
• P. 20: Since a permutation g is a function, the standard notation for its restriction to S is g|_S, not the book's g | S.
• P. 20, last line of Section 2.1: "minimal nonempty G-invariant subset".
• Pp. 20, 22: A set S is fixed by G if x^g = x for all x in S and g in G. In particular a fixed point is x such that x^G = x. Similar concepts apply to a single group element g and to any subgroup of G.
• P. 21: The set of conjugations, {τ_g: g in G}, forms a group but it need not be isomorphic to G. (If G is abelian, this group is trivial.) The conjugation mappings are known as inner automorphisms of G.
• P. 22: The standard name of Lemma 2.2.4 is "Burnside's Lemma". This name escapes the question of who first found or published it.
• P. 28: In Lemma 2.5.1, "maximal subgroup" should be "maixmal proper subgroup" (obviously!).
• P. 29: Lemma 2.6.1 is the directed form of Euler's Köningsberg Bridges theorem (about Eulerian circuits/trails/tours).
• P. 29, top: There needs to be a reason that B is not V.
• P. 32, 3d paragraph of Notes: "minimal asymmetric" should be "minimally asymmetric".
• P. 34: In the definition of a Cayley graph at the bottom, add the requirement that C generate G by products (without taking inverses). This is absolutely essential!
• Pp. 35, 36: An arc transitive graph without isolated vertices is vertex transitive. If it has isolated vertices, it is not vertex transitive (with one exception).
• P. 39, Menger's Theorem: One must assume also that u, v are not adjacent.
• P. 49, Cayley graph: Notice that the definition does *not* require that C generate the group. C could even be the empty set.
• P. 55, Exercise 12: The words "the sets of" need to be inserted before "nonidentity elements".
• P. 59: We should say that X is not s-arc transitive if it has no s-arcs.
• P. 59, bottom: An s-arc transitive graph need not be (s−1)-arc transitive. Here are two counterexamples.
  • A disconnected graph, one component being K₂ and the other C_m where m ≥ 3. It is s-arc transitive for s ≥ 2 but not for s = 1.
  • A path of length 4 with an extra edge sticking out of the middle vertex. It is connected, and it is 4-arc transitive but not 3-arc transitive.
• P. 61: Lemma 4.2.1 is false as stated. The hypothesis that f is surjective on edges is too weak. The correct hypothesis is that, for each vertex x of X, f | N_out(x) is surjective onto N_out(f(x)). Here N_out(v) means the set of heads of arcs whose tail is v.
• P. 62, "spindle": This is usually called a "theta graph".
• P. 62, Theorem 4.2.2: minimum valency at least two.
• P. 62, Proof, 4th paragraph: Since X is not a cycle, there is either an edge to a vertex not in C, or a chord of C (defined on p. 311! It is an edge not in C whose endpoints are both in C).
• P. 67, line 2: "Section 3.1", not 3.7.
• P. 67, line -2: "induced by any pair" should read "induced between any pair" since the edges within a cell aren't intended to be in the induced subgraph.
• P. 90: The original and (in my humble opinion) best definition of a Moore graph is different from the one in the book (which has become the usual one). Consider a graph of diameter d with maximum valency at most k. What is the largest number of vertices it could possibly have? A simple upper bound is
    n(k,d) := 1 + k + k(k−1) + ... + k(k−1)^d−1.
  Theorem. A graph of diameter d with maximum valency at most k, for which n = n(k,d), is k-regular with girth 2d + 1; and conversely, a k-regular graph with girth 2d + 1 has n(k,d) vertices.
• Pp. 165-167: I prefer a slightly different terminology. I call B(X) the unoriented incidence matrix of X, and I call D(X) an oriented incidence matrix of X ("an" because it's not unique). I don't like to think of B as "the incidence matrix" because, in much of graph theory, D is more important.
• P. 170, beginning of 4th paragraph: More explicitly, one could say "Any square matrix has at least one complex eigenvalue .... When A is real symmetric, that eigenvalue is real by Lemma 4.2.2. Hence a real symmetric matrix A ..."
• P. 175, line 7: "are positive and" should read "are positive. Furthermore,"
• P. 189, Exercise 2: The problem should read, "if and only if there are diagonal matrices M and N, with all diagonal entries equal to +1 or −1, such that MDN = B."
• P. 189, Exercise 5: It's assumed implicitly (in the whole book, except where they say otherwise) that V is a real vector space.
• P. 218, just above Lemma 10.1.1: There is only one class of disconnected strongly regular graphs. There are two classes of imprimitive s.r.g.s: the disconnected ones, and their complements.
• P. 220: Lemma 10.2.1 should read: "with at most three ... is strongly regular or complete." Note that the proof assumes the existence of three eigenvalues k, θ, τ that are not necessarily distinct, but it therefore assumes |V| > 2.
• P. 222, Lemma 10.3.5: A more precise statement would replace "eigenvalue θ" by "eigenvalue" and "then the parameters" by "then the eigenvalue is the larger eigenvalue, θ (rather than τ), and the parameters".
• P. 222, Lemma 10.3.5: Certainly X must be connected, because we need to know that k is a simple eigenvalue. I think the complement of X need not be connected. (The book's proof is unclear about this.)
• P. 222, line −2: Replace "0 < θ < k, and so 0 < k − θ < n/2" by "0 ≤ θ < k, and so 0 < k − θ < n/2 − 0 = n/2".
• P. 223, line −8: "2−" should be "2-" (hyphen, not minus sign).
• P. 223, line 2: I do not see why −k &lew; τ. I do see that k − τ < n can be deduced if X is primitive. If X is imprimitive but disconnected, it can be deduced from knowing the form of the complement (Lemma 10.1.1).
• P. 224, line 8: "occurs twice" should be "occurs once".
• P. 225, bottom displayed equation: The summations should be products, since the group is written multiplicatively.
• P. 231, Theorem 10.7.1: There should be no box at the end of the statement. The proof ends near the bottom of page 234.
• P. 236, line −5: "the next chapter" should read "Chapter 12".
• P. 238, strategy in second paragraph: The statement that X has no induced 4-cycles is false (see Lemma 10.9.2). It is true that any induced 4-cycle has to be of a particular form, in relation to the distance partition from any of its vertices. I am not sure exactly how to fix this proof strategy (except for t = 1).
• P. 250: In the older literature the Seidel matrix is also called the (0,−1,+1)-adjacency matrix, and similar names.
• P. 252, Lemma 11.3.1, last line: 1/α is an integer, not α.
• P. 252, line −3: "the stated expression for n."
• Chapter 11, esp. p. 255: A switching class of graphs is not "also known as a two-graph." A two-graph is a class of (unordered) triples of vertices, such that each quadruple contains an even number of triples belonging to the two-graph. There is a theorem that there is a one-to-one correspondence between switching classes of graphs on vertex set V and two-graphs on vertex set V, but having a bijection does not make them the same thing.
• P. 255, bottom: The "switching graph" is, I think, a mistake for the graph known as the double covering graph, or double cover, of the signed complete graph K_X (the signed complete graph whose adjacency matrix is S(X)). This can also be called the double cover of K_n that corresponds to X. (The double cover appears in Biggs, Algebraic Graph Theory, Exercise 19A.)
    Here is the definition of the double cover of K_X: If uv is an edge, then join (u,i) to (v,i+1) (addition modulo 2). If uv is not an edge, join (u,i) to (v,i). (Think of the 0 and 1 as signs, since Z₂ is isomorphic to {+,−}.)
    To define the double cover of a signed graph Σ: The vertex set is V(Σ) × Z₂. If uv is a negative edge, then join (u,i) to (v,i+1) (addition modulo 2). If uv is a positive edge, join (u,i) to (v,i). This definition is motivated by aspects of signed graph theory.
• P. 266, generalized line graph: Their definition is not the usual one. The usual definition is due to Hoffman[4]; it involves attaching cocktail-party graphs CP(n) to each vertex of the line graph.
• P. 267, Lemma 12.3.1: "fixes L" should be "leaves L invariant". "Fix" often (usually?) means fixing pointwise. That is not what happens.
• P. 268: The definition of a root system is incomplete. We need to add: (c) For any two roots r and s, the quantity 2 (r·s)/(r·r) is an integer. See Exercise 12.A7.
• P. 268, Lemma 12.4.1: n should be ≥ 3.
• P. 269, Proof of Theorem 12.4.2: I'm not sure it's justified to exchange the roles of b and − a − b, because b is given in advance. (I could be mistaken.)
• P. 270, Proof of Lemma 12.5.2: Line 4 should say <−b−x> is in L, not −b−x in L.
• P. 372: Perhaps another "ultimate generalization" of Murasugi (and Traldi, and Fortuin-Kasteleyn) is found in T. Zaslavsky, Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc. 334 (1992), 317-347. This is "ultimate" in a different way from [2] cited in the text. A truly ultimate generalization would combine this and [2], but that has not been done yet.
• INDEX
  • partition, p. ?
  • cell of a partition, p. ?
  • Coxeter graph, p. 69
  • design, p. 94
  • Folkman graph, pp. 36, 54
  • t-design, p. 94

  ---

  To the main course page.

  To my home page.