2015 PhD Summer School in Discrete Mathematics

Classifying vertex-transitive graphs by their arc-types

Not scheduled

1m

Rogla, Slovenia

Speaker

Prof. Marston Conder (University of Auckland)

Description

Locally-finite vertex-transitive graphs may be classified according to the action of the automorphism group on the arcs (ordered edges) of the graph. Let $X$ be vertex-transitive graph of valency $d$, with full automorphism group $A$. Then the {\em arc-type\/} of $X$ is defined in terms of the lengths of the orbits of the action of the stabiliser $A_v$ of a given vertex $v$ on the set of arcs emanating from $v$. Specifically, the arc-type is the partition of $d$ as the sum $$n_1+n_2+\cdots +n_t+(m_1+m_1)+(m_2+m_2)+\cdots +(m_s+m_s),$$ where $n_1,n_2,\dots ,n_t$ are the lengths of the self-paired orbits, and $m_1,m_1,m_2,$ $m_2,\dots ,m_s,m_s$ are the lengths of the non-self-paired orbits. %, in descending order. This is a graph invariant. For example, if $X$ is arc-transitive then its arc-type is $d$, while if $X$ is half-arc-transitive then its arc-type is $(d/2+d/2)$, and if $X$ is zero-symmetric (or equivalently a graphical regular representation of the group $A$), then $n_i=1$ and $m_j=1$ for all $i$ and $j$. In this talk I will explain how it can be shown that every partition of the given form occurs as the arc-type of some vertex-transitive graph, with the exception of $1+1$ and $(1+1)$. The proof uses Cartesian products of `relatively prime' examples of specially chosen VT graphs. This is joint work with Toma\v{z} Pisanski and Arjana \v{Z}itnik (Ljubljana).