School Seminars and Colloquia

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