School Seminars and Colloquia

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