Symmetric Graphs and Flag Graphs
by
Sanming Zhou
The University of Melbourne

A graph X is said to be a G-symmetric graph if it admits G as a group of automorphisms such that G is transitive on the ordered pairs of adjacent vertices of X. If moreover the vertex set of X admits a nontrivial G-invariant partition B, then X is called an imprimitive G-symmetric graph. For such a graph X a natural 1-design D(B) can be associated with a block B of B. In a vast number of cases the dual 1-design of D(B) contains no repeated blocks, and in the talk we will present a construction of all (up to isomorphism) imprimitive G-symmetric graphs with this property. The constructed graphs, called flag graphs, have vertex sets certain G-orbits on the flags of some G-point- and G-block-transitive 1-designs. The inspiration for the construction is the 3-arc graph construction introduced earlier by Li, Praeger and the speaker.

Date received: November 14, 2000