Premium
Locally s ‐distance transitive graphs
Author(s) -
Devillers Alice,
Giudici Michael,
Li Cai Heng,
Praeger Cheryl E.
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20574
Subject(s) - mathematics , combinatorics , discrete mathematics , vertex transitive graph , cograph , symmetric graph , 1 planar graph , indifference graph , line graph , vertex (graph theory) , graph , voltage graph
We give a unified approach to analyzing, for each positive integer s , a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s ‐arc transitive graphs of diameter at least s . A graph is in the class if it is connected and if, for each vertex v , the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v , for each i from 1 to s . We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s ≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012