# A construction of imprimitive symmetric graphs

*Discrete Structures and Algorithms (Seminar)*

*by Bin Jia*

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

*Date: Mon 30th May 2011*

*Time: 4:15 PM*

*Location: Hercus Theatre (L105, 1st floor) David Caro Building (Physics), The University of Melbourne*

*Abstract*: Let G be a finite simple graph without isolated vertices. An automorphism of G is a permutation of its vertices that preserves the adjacency and non-adjacency relations. G is called symmetric if any arc (ordered pair of adjacent vertices) can be mapped to any other arc by some automorphism. G is imprimitive with respect to an arc-transitive subgroup of its automorphism group if its vertex set admits a non-trivial partition P that is invariant under the action of the subgroup. In this case the quotient graph is defined to have vertex set P such that two blocks are adjacent if and only if an edge of G between them exists.

For any two adjacent blocks of P, if not all vertices of one block have neighbours in the other, then G is not a multicover of the quotient graph. In this case we give a combinatorial method for reconstructing the imprimitive graph from certain natural local structures of its quotient.

This talk is aimed at a general audience. We will display most of ideas and results by pictures. The talk is based on joint work with Lu and Wang.

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