Skip to main content
main-content

Über dieses Buch

Ever since the discovery of the five platonic solids in ancient times, the study of symmetry and regularity has been one of the most fascinating aspects of mathematics. Quite often the arithmetical regularity properties of an object imply its uniqueness and the existence of many symmetries. This interplay between regularity and symmetry properties of graphs is the theme of this book. Starting from very elementary regularity properties, the concept of a distance-regular graph arises naturally as a common setting for regular graphs which are extremal in one sense or another. Several other important regular combinatorial structures are then shown to be equivalent to special families of distance-regular graphs. Other subjects of more general interest, such as regularity and extremal properties in graphs, association schemes, representations of graphs in euclidean space, groups and geometries of Lie type, groups acting on graphs, and codes are covered independently. Many new results and proofs and more than 750 references increase the encyclopaedic value of this book.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Special Regular Graphs

Abstract
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 = b0. The sequence
$$\iota (\Gamma ): = \{ {{b}_{0}},{{b}_{1}}, \cdots ,{{b}_{{d - 1}}};{{c}_{1}},{{c}_{2}}, \cdots ,{{c}_{d}}\} ,$$
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
$${{a}_{i}} = k - {{b}_{i}} - {{c}_{i}}\;(i = 0, \ldots ,d) $$
(1)
is the number of neighbours of δ in Γ i (γ) for d(γ,δ) = i, are called the intersection numbers of Γ. Clearly
$$\begin{array}{*{20}{c}} {{{b}_{0}} = k,} & {{{b}_{d}} = {{c}_{0}} = 0,} & {{{c}_{1}} = 1.} \\ \end{array}$$
(2)
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 2. Association Schemes

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 3. Representation Theory

Abstract
Motivated by applications to the classification of certain distance-regular graphs we consider representations of graphs by sets of vectors in a Euclidean space.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 4. Theory of Distance-Regular Graphs

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 5. Parameter Restrictions for Distance-Regular Graphs

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 6. Classification of the Known Distance-Regular Graphs

Abstract
In this chapter we classify distance-regular graphs with diameter d ≥ 3 into the following four (non-exclusive) classes:
(i)
graphs with classical parameters,
 
(ii)
partition graphs,
 
(iii)
regular near polygons,
 
(iv)
the remaining distance-regular graphs.
 
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 7. Distance-Transitive Graphs

Abstract
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).
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 8. Q-polynomial Distance-Regular Graphs

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 9. The Families of Graphs with Classical Parameters

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 10. Graphs of Coxeter and Lie Type

Abstract
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].
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 11. Graphs Related to Codes

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 12. Graphs Related to Classical Geometries

Abstract
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).
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 13. Sporadic Graphs

Abstract
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.
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Chapter 14. Tables of Parameters for Distance Regular Graphs

Abstract
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).
Andries E. Brouwer, Arjeh M. Cohen, Arnold Neumaier

Backmatter

Weitere Informationen