Graph View

Backlinks

The Library

Search

SearchSearch

Distance Transitive Graph

Mar 10, 2025, 3 min read

  • 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.

  • (Godsil e4.14) An -arc transitive graph with girth has diameter and is distance transitive.

    • Let be this graph, and . Let be a shortest path between and . If then must contain an -arc which can be mapped to an -arc in the cycle of length . However, the distance between two vertices in this cycle is at most which would yield a shorter shortest path. Therefore . Additionally, any two points in the cycle have distance at most . Therefore, . Therefore .

      Let be the shortest path between and . Clearly since the diameter is and so can be mapped to any other -arc by automorphism because of -arc transitivity. Therefore, shortest paths are preserved and so are distances. Therefore, is also distance transitive .

Links