School Seminars and Colloquia

Vertex-transitive graphs with given arc-type

Discrete Structures and Algorithms (Seminar)

by Nemanja Poznanovic

Institution: The University of Melbourne
Date: Thu 25th May 2017
Time: 11:00 AM
Location: Room 107, Peter Hall building

Abstract: Vertex-transitive graphs play a central role in algebraic graph theory. We will begin this talk by discussing some basic properties of these graphs and explaining how they may be classified using the language of arc-types.

The arc-type of a vertex-transitive graph is a partition of the graph's valency written as a sum of the lengths of the orbits of a vertex-stabilizer acting on the neighbourhood of that vertex. Parentheses are used in the partition to denote paired orbits.

A natural question which arises is which integer partitions (marked with parentheses) occur as the arc-type of some vertex-transitive graph. It has been shown by Conder, Pisanski and Zitnik that every marked integer partition except for 2 = 1+1 and 2 = (1+1) is the arc-type of some vertex-transitive graph. Recently, we have extended this result by showing that every marked integer partition except for 1, 1+1 and (1+1) is the arc-type of infinitely many connected Cayley graphs. We will discuss both of these results and some consequences.

No prior knowledge of vertex-transitive graphs is assumed.

For More Information: Contact: Sanming Zhou. email: