Triple Transitive Graphs

The graph G is n‐tuple transitive if for every pair of ordered sets ( u 2 , u 2 , …, u n ), ( v 1 , v 2 , …, v n ) each of n distinct vertices of G , such that ∂( u i , u j ) = ∂( u i , v j ) for all 1 ⩽ i < j ⩽ n there is an automorphism α of G such that α u i = v i , 1 ⩽ i ⩽ n . Thus n ‐tuple transitivity is a generalization of distance transitivity. It is shown that each triple transitive graph that is not of form K 1, m is distance transitive, and if it is not a cycle, then it has girth 3 or 4. The number of such graphs of girth 4 and valency k is finite for each k ⩾ 3. Examples of triple transitive graphs include the graph of the k ‐dimensional “cube” Q k , and another graph of girth 4 derived from it for each odd k ⩾ 5.