Premium
Triple Transitive Graphs
Author(s) -
Meredith G. H. J.
Publication year - 1976
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-13.2.249
Subject(s) - combinatorics , odd graph , transitive relation , mathematics , transitive reduction , valency , symmetric graph , discrete mathematics , triangle free graph , graph , vertex transitive graph , automorphism group , automorphism , chordal graph , graph power , 1 planar graph , voltage graph , line graph , linguistics , philosophy
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.