Distance-Regular Graphs

A connected graph Г is called distance-regular if there are integers b _i , c _i (i ≥ 0) such that for any two points γ, δ ε Г at distance i = d(γ,δ), there are precisely c _i neighbours of δ in Г_i−1(γ) and b _i neighbours of δ in Г_i+1(γ). In particular, Г is regular of valency k = b₀. The sequence

where d is the diameter of Г, is called the intersection array of Г (cf. Biggs [71]); the numbers c _i , b _i , and a _i , where

is the number of neighbours of δ in Γ _i (γ) for d(γ,δ) = i, are called the intersection numbers of Γ. Clearly

The first part of this chapter contains a short account of the basic theory of (symmetric) association schemes. Such schemes are essentially partitions of a complete graph into regular subgraphs which are interrelated in a specific way. For a more extensive treatment, see Bannai & Ito [33]. The last part of this chapter treats some special topics. Although we shall develop large parts of the theory of distance-regular graphs independently of the results of this chapter, we shall use concepts and results about association schemes for more specialized topics such as, e.g., Q-polynomial orderings (Chapter 8) and codes in graphs (Chapter 11). Multiplicity formulas (2.2.2) and bounds (2.3.3) as well as the Krein conditions (2.3.2) developed here in general context will recur for distance-regular graphs in Chapter 4.

Motivated by applications to the classification of certain distance-regular graphs we consider representations of graphs by sets of vectors in a Euclidean space.

We now come to the central topic of the book. The first section may be viewed as a short introduction to the subject. Although we shall develop large parts of the theory of distance-regular graphs independently of Chapter 2, we shall use concepts and results about association schemes for more specialized topics such as Q-polynomial orderings (Chapter 8) and codes in graphs (Chapter 11). In §4.2 we look at various constructions that, given a distance-regular graph, produce a new one. In §4.3 we show how certain conditions on the parameters force the presence of substructures, like lines or Petersen subgraphs. In §4.4 we use the results of Chapter 3 to obtain a characterization by parameters of the two most basic families of distance-regular graphs, the Johnson and Hamming graphs. Chapter 5 contains most of the known conditions on the parameters, Chapter 6 classifies the known distance-regular graphs in various families, Chapter 7 is concerned with distance-transitive graphs, Chapter 8 discusses the consequences of the Q-polynomial property, and the remaining chapters give all examples known to us.

In this chapter we collect most of the restrictions on intersection arrays of distance-regular graphs known to us. (A few very basic facts have already been mentioned in §4.1D.) Some of these restrictions are important tools in the theoretical investigation of the properties of distance-regular graphs, like the unimodality of the sequence (k _i ) _i discussed in §5.1. (We already used this on several occasions.) Various bounds on the diameter in terms of the valency are theoretically important. First we have Terwilliger’s diameter bound for the case where the graph contains a quadrangle; next Ivanov’s theory, which yields abound on the diameter for arbitrary distance-regular graphs with fixed numerical girth, and finally the work by Bannai & Ito, who strive to remove the dependency on the girth from these bounds. Also Godsil proved diameter bounds, but this time in terms of a multiplicity.

In this chapter we classify distance-regular graphs with diameter d ≥ 3 into the following four (non-exclusive) classes:

There are only finitely many distance-transitive graphs with given valency > 2. This result was first shown in Cameron, Praeger, Saxl & Seitz [183] by use of the classification of finite simple groups. Below we give a proof due to Weiss [779] which is independent of this classification. A basic ingredient to the proof of Weiss’ theorem is the celebrated Thompson-Wielandt Theorem. The proof of the latter theorem requires group-theoretic preparation which can be found in Section 7.1. The Thompson-Wielandt Theorem is the content of Section 7.2 and Weiss’ theorem is in Section 7.3. Subsequently we discuss results in the cases of large girth (Section 7.4), small valency (Section 7.5), and imprimitive graphs (Section 7.6). The state of the art in overall classification and a few related results are given in the final sections (7.7–8).

In this chapter we discuss in detail the relations between the parameters of Q-polynomial distance-regular graphs and their Q-sequences. We start with a reformulation of the Q-polynomial property defined in §4.1E, which is the source of most of our results. This leads to a three-term recurrence relation for Q-sequences (Theorem 8.1.2) discovered by Leonard [485], and a representation of the intersection array of Q-polynomial graphs in terms of 5 parameters only (Proposition 8.1.5). We mention Leonard’s explicit parameter formulae and results of Bannai & Ito [33] on the integrality of eigenvalues for large diameters based on these formulae. We also determine which of the known distance-regular graphs are Q-polynomial.

In this chapter we discuss the known infinite families of graphs with classical parameters, except for some graphs of Lie type, treated in the next chapter. A few sporadic graphs with classical parameters can be found in Chapters 3 and 11, cf. Table 6.1.

In this chapter we study Coxeter systems and Tits systems and certain graphs derived from these. In the first few sections finiteness is not assumed. In the later sections almost all known infinite families of distance-transitive graphs are described in this framework. The chapter ends with a determination of all distance-transitive graphs which naturally arise from a Tits system in a finite Chevalley group. Much more information on Tits systems, Chevalley groups and buildings can be found in Bourbaki [113], Carter [187, 188] and Tits [747, 753].

Let \(V = F_{q}^{n} \) be the vector space of n-tuples with entries in the finite field F _q with q elements, and let C be a linear code in V (i.e., a linear subspace of V). We define the coset graph Γ(C) of C by taking as vertices the cosets of C in V, and joining two cosets when they have representatives that differ in one coordinate (i.e., have Hamming distance one). In some cases Γ(C) turns out to be distance-regular. In section 11.1 we study this phenomenon in a more general setting. Instead of the vector space V (that is, instead of the Hamming graph H(n,q)), we take an arbitrary distance-regular graph Γ, and instead of the partition of V into cosets of C, we take an arbitrary partition Π of Γ, Now there is an obvious concept of quotient graph Γ / Π generalizing that of coset graph, and Theorem 11.1.6 gives a sufficient condition for this quotient graph to be distance-regular. Section 11.1 is the outgrowth of earlier discussions with A.R. Calderbank.

Graphs on isotropic points of a classical geometry (i.e., a geometry related to a semilinear or quadratic form) have been studied explicitly in Chapter 9 and implicitly in the context of parabolic representations of groups of Lie type. The nonisotropic points usually fall into a few orbits of the isometry group. The permutation rank of these orbits depends on the cardinality of the underlying field. We show that only in a few cases the related graphs are distance-regular. In the last three sections we construct several infinite families of antipodal covers of complete graphs (starting from affine instead of projective points), and an infinite family of partial geometries yielding bipartite distance-regular graphs of diameter 4 (starting from complete arcs in a projective plane).

The preceding four chapters were concerned with graphs belonging to an infinite series of distance-regular graphs or constructed in a uniform way. A handful of (known) distance-regular graphs remain. These are the subject of the present chapter.

This chapter contains tables of parameters for primitive distance-regular graphs with diameter 3 on at most 1024 vertices, for non-bipartite distance-regular graphs with diameter 4 on at most 4096 vertices, and for arbitrary distance-regular graphs of diameter at least 5 on at most 4096 vertices. In each category the parameter sets are ordered by k (not v). We only list intersectiòn arrays that pass all feasibility criteria known to us. We do not give any information on the polygons (e.g., these have many P- and Q-polynomial structures).