4 - Orbital Graphs and Strongly Regular Graphs

Summary

In this chapter we shall define and explore the most basic properties of what are called orbital graphs. We shall see that, analogously to coset graphs, any vertex-transitive graph is a (generalised) orbital graph. Moreover, this description gives us, in principle, a criterion for arc-transitivity. Consideration of a special type of orbital graph will lead us to strongly regular graphs.

Definitions and basic properties

We have seen in Chapter 1 that, given a permutation group (Γ, V), there is a natural induced action (Γ, V × V) on the ordered pairs of elements of V. We shall now study this action in more detail. First, let us henceforth, unless stated otherwise, suppose in this chapter that the action of Γ on V is transitive. Then the orbits of Γ on V × V are called orbitals. One of them is {(u, u) : u ∈ V}, because (Γ, V) is transitive. We denote this orbital by D0 and we call it the trivial orbital. We usually list the orbitals as D₀,D₁, …,D_r−1. The number r of orbitals of (Γ, V × V) is called the rank of (Γ, V).

The transpose A^T of a subset A of V × V (and, in particular, of any orbital) is defined by A_T = {(v, u) : (u, v) ∈ A}. We say that a subset A of V × V, and therefore any orbital, is self-paired when A = A^T. A self-paired set containing the two arcs (u, v) and (v, u) is considered to be the edge {u, v}. Note that an orbital D is either self-paired or it contains no pair of opposite arcs. In fact, D ∩ D ^T ≠ Ø implies D = D^T.

Obviously the rank r of (Γ, V) satisfies r ≥ 2 unless V has one element. The case r = 2 clearly corresponds to a 2-transitive permutation group, and we have already seen that such groups are not very interesting as automorphism groups of graphs. From our point of view, therefore, the first interesting case occurs when r = 3. We shall look at this particular case in more detail later in this chapter. We also note that, from now on, any orbital mentioned will be assumed to be nontrivial unless explicitly stated otherwise.