# Imprimitive symmetric graphs with cyclic blocks

*Discrete Structures and Algorithms (Seminar)*

*by Sanming Zhou*

*Institution:*The University of Melbourne, Mathematics and Statistics Department

*Date: Tue 21st July 2009*

*Time: 2:15 PM*

*Location: Room 107, Richard Berry Building, The University of Melbourne*

*Abstract*: This talk is based on a joint paper with Cai Heng Li and Cheryl Praeger. A graph X is symmetric if its automorphism group Aut(X) is transitive on the set of arcs (oriented edges) of X.

If a subgroup G of Aut(X) acts transitively on the set of arcs of X and leaves invariant a nontrivial partition of the vertex set, then X is called an imprimitive G-symmetric graph. We study such graphs satisfying the following conditions: for two parts B, C of the partition, either there is no edge of X between B and C, or exactly two vertices of B lie on no edge with a vertex of C; and as C runs over all parts adjacent to B these vertex pairs (ignoring

multiplicities) form a cycle. We prove that this occurs if and only if the size of each part of the partition is 3 or 4, and moreover we give constructions of three infinite families of such graphs. I will also mention recent progress on a problem arising from our results.

*For More Information:* contact: David Wood. email woodd@unimelb.edu.au