Distance Transitive Graph

• A connected graph is distance transitive if given any two order pairs and such that , there is an automorphism of such that

• Distance transitive graphs are at least -arc transitive.

• An alternate characterization is provided as follows Let be the set of vertices at distance from and the diameter of the graph. The partition

  is the distance partition with respect to

  • acts transitively on . Thus, each cell in the distance partition acts as an orbit of
  • If has diameter , then acts distance transitively on if and only if it acts transitively and for any , the stabilizer has exactly orbits.
  • The graph induced by any cell in the partition is regular.
  • The graph induced by any pair of cells is semi-regular.

• The parameters of a distance transitive graph are a set of triple for . Let , = number of vertices is adjacent to in = number of vertices is adjacent to in = number of vertices is adjacent to in

  • The intersection array is a matrix recording these parameters
  • where is the degree of the graph.
  • An abbreviated version of the intersection array is simply

• is distance regular if the intersection array is well defined and the same for each vertex.

  • Every distance transitive graph is distance regular. But the converse is not necessarily true.

Links §

• Algebraic Graph Theory by Godsil and Royle