Symmetry in Graphs - Part II
Org: Joy Morris
(University of Lethbridge)
- MICHAEL GIUDICI, University of Western Australia
Arc-transitive bicirculants [PDF]
A graph on $2n$ vertices is a bicirculant if it admits an automorphism that is a permutation with two cycles of length $n$. For example, the Petersen and Heawood graphs. Arc-transitive bicirculants of valencies three, four and five have previously been classified by various authors. In this talk I will discuss recent joint work with Alice Devillers and Wei Jin that characterises all arc-transitive bicirculants and provides a framework for their complete classification.
- KLAVDIJA KUTNAR, University of Primorska
Hamilton paths of cubic vertex-transitive graphs [PDF]
In 1969 Lovasz posed the problem of constructing a vertex-transitive graph without a Hamilton path. After 50 years no such graph has been found. Only five known vertex-transitive graphs without a Hamilton cycle (but with a Hamilton path) exist: $K_2$ and four cubic graphs (the Petersen graph, the Coxeter graph, and two graphs obtained from these by replacing each vertex with a triangle). Therefore concentrating on cubic graphs is a reasonable starting point for Lovasz's problem.
In this talk I present recent ideas, and partial results regarding construction of Hamilton cycles in cubic vertex-transitive graphs with a primitive automorphism group.
- JOY MORRIS, University of Lethbridge
Almost all Cayley digraphs are DRRs [PDF]
A Digraphical Regular Representation (DRR) of a group $G$ is a digraph whose automorphism group is $G$ acting regularly on its vertices. A Cayley digraph is a digraph whose automorphism group contains some group acting regularly on its vertices. In 1982 Babai and Godsil conjectured that as $n$ tends to infinity, for every group of order $n$ the proportion of Cayley digraphs on $n$ vertices that are DRRs tends to 1, and proved this for Cayley graphs on some families of groups. I will discuss joint work with Pablo Spiga in which we prove this conjecture.
- GABRIEL VERRET, University of Auckland
An update on the Polycirculant Conjecture [PDF]
One version of the Polycirculant Conjecture is that every finite vertex-transitive digraph admits a nonidentity semiregular automorphism. (That is, an automorphism which, when viewed as a permutation, has all cycles of the same length.) I will give an overview of the status of this conjecture, as well as describe some recent progress with Michael Giudici.