Algebraic Graph Theory

Frontmatter

1. Graphs

Abstract

In this chapter we undertake the necessary task of introducing some of the basic notation for graphs. We discuss mappings between graphs—isomorphisms, automorphisms, and homomorphisms—and introduce a number of families of graphs. Some of these families will play a significant role in later chapters; others will be used to illustrate definitions and results.

Chris Godsil, Gordon Royle

2. Groups

Abstract

The automorphism group of a graph is very naturally viewed as a group of permutations of its vertices, and so we now present some basic information about permutation groups. This includes some simple but very useful counting results, which we will use to show that the proportion of graphs on n vertices that have nontrivial automorphism group tends to zero as n tends to infinity. (This is often expressed by the expression “almost all graphs are asymmetric”) For a group theorist this result might be a disappointment, but we take its lesson to be that interesting interactions between groups and graphs should be looked for where the automorphism groups are large. Consequently, we also take the time here to develop some of the basic properties of transitive groups.

Chris Godsil, Gordon Royle

3. Transitive Graphs

Abstract

We are going to study the properties of graphs whose automorphism group acts vertex transitively. A vertex-transitive graph is necessarily regular. One challenge is to find properties of vertex-transitive graphs that are not shared by all regular graphs. We will see that transitive graphs are more strongly connected than regular graphs in general. Cayley graphs form an important class of vertex-transitive graphs; we introduce them and offer some reasons why they are important and interesting.

Chris Godsil, Gordon Royle

4. Arc-Transitive Graphs

Abstract

An arc in a graph is an ordered pair of adjacent vertices, and so a graph is arc-transitive if its automorphism group acts transitively on the set of arcs. As we have seen, this is a stronger property than being either vertex transitive or edge transitive, and so we can say even more about arc-transitive graphs. The first few sections of this chapter consider the basic theory leading up to Tutte’s remarkable results on cubic arc-transitive graphs. We then consider some examples of arc-transitive graphs, including three of the most famous graphs of all: the Petersen graph, the Coxeter graph, and Tutte’s 8-cage.

Chris Godsil, Gordon Royle

5. Generalized Polygons and Moore Graphs

Abstract

A graph with diameter d has girth at most 2d + 1, while a bipartite graph with diameter d has girth at most 2d. While these are very simple bounds, the graphs that arise when they are met are particularly interesting. Graphs with diameter d and girth 2d + 1 are known as Moore graphs. They were introduced by Hoffman and Singleton in a paper that can be viewed as one of the prime sources of algebraic graph theory. After considerable development, the tools they used in this paper led to a proof that a Moore graph has diameter at most two. They themselves proved that a Moore graph of diameter two must be regular, with valency 2, 3, 7, or 57. We will provide the machinery to prove this last result in our work on strongly regular graphs in Chapter 10.

Chris Godsil, Gordon Royle

6. Homomorphisms

Abstract

Although any isomorphism between two graphs is a homomorphism, the study of homomorphisms between graphs has quite a different flavour to the study of isomorphisms. In this chapter we support this claim by introducing a number of topics involving graph homomorphisms. We consider the relationship between homomorphisms and graph products, and in particular a famous unsolved conjecture of Hedetniemi, which asserts that if two graphs are not n-colourable, then neither is their product. Our second major topic is the exploration of the core of a graph, which is the minimal subgraph of a graph that is also a homomorphic image of the graph. Studying graphs that are equal to their core leads us to an interesting class of graphs first studied by Andrásfai. We finish the chapter with an exploration of the cores of vertex-transitive graphs.

Chris Godsil, Gordon Royle

7. Kneser Graphs

Abstract

The Kneser graph K _v:r is the graph with the r-subsets of a fixed v-set as its vertices, with two r-subsets adjacent if they are disjoint. We have already met the complete graphs K _v:1, while K _v:2 is the complement of the line graph of K _v . The first half of this chapter is devoted to fractional versions of the chromatic number and clique number of a graph. We discover that for the fractional chromatic number, the Kneser graphs play a role analogous to that played by the complete graphs for the ordinary chromatic number. We use this setting to provide a proof of the Erdős-Ko-Rado theorem, which is a famous result from extremal set theory. In the remainder of the chapter, we determine the chromatic number of the Kneser graphs, which surprisingly uses a nontrivial result from topology, and study homomorphisms between Kneser graphs.

Chris Godsil, Gordon Royle

8. Matrix Theory

Abstract

There are various matrices that are naturally associated with a graph, such as the adjacency matrix, the incidence matrix, and the Laplacian. One of the main problems of algebraic graph theory is to determine precisely how, or whether, properties of graphs are reflected in the algebraic properties of such matrices.

Chris Godsil, Gordon Royle

9. Interlacing

Abstract

If M is a real symmetric n × n matrix, let θ ₁(M) ≥ θ ₂(M) ≥ ... ≥ θ _n (M) eigenvalues in nonincreasing order. Suppose A is a real symmetric n × n matrix and B is a real symmetric m × m matrix, where m ≤ n. We say that the eigenvalues of B interlace the eigenvalues of A if for i = 1,..., m,

$$ \theta _{n - m + i} (A) \leqslant \theta _i (B) \leqslant \theta _i (A). $$

Chris Godsil, Gordon Royle

10. Strongly Regular Graphs

Abstract

In this chapter we return to the theme of combinatorial regularity with the study of strongly regular graphs. In addition to being regular, a strongly regular graph has the property that the number of common neighbours of two distinct vertices depends only on whether they are adjacent or nonadjacent. A connected strongly regular graph with connected complement is just a distance-regular graph of diameter two. Any vertex-transitive graph with a rank-three automorphism group is strongly regular, and we have already met several such graphs, including the Petersen graph, the Hoffman-Singleton graph, and the symplectic graphs of Section 8.11.

Chris Godsil, Gordon Royle

11. Two-Graphs

Abstract

The problem that we are about to discuss is one of the founding problems of algebraic graph theory, despite the fact that at first sight it has little connection to graphs. A simplex in a metric space with distance function d is a subset S such that the distance d(x, y) between any two distinct points of S is the same. In ℝ ^d , for example, a simplex contains at most d + 1 elements. However, if we consider the problem in real projective space then finding the maximum number of points in a simplex is not so easy. The points of this space are the lines through the origin of ℝ ^d , and the distance between two lines is determined by the angle between them. Therefore, a simplex is a set of lines in ℝ ^d such that the angle between any two distinct lines is the same. We call this a set of equiangular lines. In this chapter we show how the problem of determining the maximum number of equiangular lines in ℝ ^d can be expressed in graph-theoretic terms.

Chris Godsil, Gordon Royle

12. Line Graphs and Eigenvalues

Abstract

If X is a graph with incidence matrix B, then the adjacency matrix of its line graph L(X) is equal to B ^T B-2I. Because B ^T B is positive semidefinite, it follows that the minimum eigenvalue of L(X) is at least −2. This chapter is devoted to showing how close this property comes to characterizing line graphs. The main result is a beautiful characterization of all graphs with minimum eigenvalue at least −2. One surprise is that the proof uses several seemingly unrelated combinatorial objects. These include generalized quadrangles with lines of size three and root systems, which arise in connection with a number of important problems, including the classification of Lie algebras.

Chris Godsil, Gordon Royle

13. The Laplacian of a Graph

Abstract

The Laplacian is another important matrix associated with a graph, and the Laplacian spectrum is the spectrum of this matrix. We will consider the relationship between structural properties of a graph and the Laplacian spectrum, in a similar fashion to the spectral graph theory of previous chapters. We will meet Kirchhoff’s expression for the number of spanning trees of a graph as the determinant of the matrix we get by deleting a row and column from the Laplacian. This is one of the oldest results in algebraic graph theory. We will also see how the Laplacian can be used in a number of ways to provide interesting geometric representations of a graph. This is related to work on the Colin de Verdiere number of a graph, which is one of the most important recent developments in graph theory.

Chris Godsil, Gordon Royle

14. Cuts and Flows

Abstract

Let X be a graph with an orientation σ and let D be the incidence matrix of X ^σ. In this chapter we continue the study of how graph-theoretic properties of X are reflected in the algebraic properties of D. As previously, the orientation is merely a device used to prove the results, and the results themselves are independent of which particular orientation is chosen. Let ℝ ^E and ℝ ^v denote the real vector spaces with coordinates indexed by the edges and vertices of X, respectively. Then the column space of D ^T is a subspace of ℝ ^E , called the cut space of X. The orthogonal complement of this vector space is called the flow space of X.

Chris Godsil, Gordon Royle

15. The Rank Polynomial

Abstract

One goal of this chapter is to introduce the rank polynomial of a signed graph, which we will use in the next chapter to construct the Jones polynomial of a knot. A second goal is to place this polynomial in a larger context. The rank polynomial is a classical object in graph theory, with a surprising range of ramifications. We develop its basic theory and provide an extensive description of its applications.

Chris Godsil, Gordon Royle

16. Knots

Abstract

A knot is a closed curve of finite length in ℝ³ that does not intersect itself. Two knots are equivalent if one can be deformed into the other by moving it around without passing one strand through another. (We will define equivalence more formally in the next section). One of the fundamental problems in knot theory is to determine whether two knots are equivalent. If two knots are equivalent, then this can be demonstrated: For example, we could produce a video showing one knot being continuously deformed into the other. Unfortunately, if two knots are not equivalent, then it is not at all clear how to prove this. The main approach to this problem has been the development of knot invariants: values associated with knots such that equivalent knots have the same value. If such an invariant takes different values on two knots, then the two knots are definitely not equivalent.

Chris Godsil, Gordon Royle

17. Knots and Eulerian Cycles

Abstract

This chapter provides an introduction to some of the graph theory associated with knots and links. The connection arises from the description of the shadow of a link diagram as a 4-valent plane graph. The link diagram is determined by a particular eulerian tour in this graph, and consequently many operations on link diagrams translate to operations on eulerian tours in plane graphs. The study of eulerian tours in 4-valent plane graphs leads naturally to the study of a number of interesting combinatorial objects, such as double occurrence words, chord diagrams, circle graphs, and maps. Questions that are motivated by the theory of knots and links can often be clarified or solved by being reformulated as a question in one of these different contexts.

Chris Godsil, Gordon Royle

Backmatter