On Automorphisms of the Double cover of circulant graphs

Canonical bipartite double cover of a graph $X$ is defined to be the graph $BX coloneqq Xtimes K_2$. The group $Aut Xtimes S_2$ naturally appears as a subgroup of $Aut BX$. In case $Aut BX cong Aut X times S_2$, the graph $X$ is called stable. Otherwise, it is unstable. If $X$ is additionally connected, non-bipartite and distinct vertices have distinct sets of neighbors, it is called non-trivially unstable. The behavior of $Aut(Xtimes Y)$, with $X$ non-bipartite and $Y$ bipartite, heavily depends on the particular case of $Aut BX$, where we take $Y=K_2$.

Known results about stability of Cayley graphs on cyclic (and more generally, abelian) groups of odd order are discussed. Circulant graphs are Cayley graphs of cyclic groups. In his work on symmetries of unstable graphs, Steve Wilson introduced several conditions implying instability of circulants of even order, referred to as Wilson types in the literature. It has also been conjectured that these conditions can explain all instability in circulant graphs.

Corrections, both old and new, and generalizations of Wilson types are discussed. In addition to revisiting already known counterexamples to the conjecture, obtained results are used to construct new infinite families of counterexamples. It is established that every non-trivially unstable circulant of order $2p$, $p$ an odd prime, has a Wilson type. It is also established that the same holds for every non-trivially unstable circulant of valency at most $7$.

This is joint work with Ademir Hujdurović and Dave Witte Morris.

Join the Zoom Meeting Here.

See you there!

Everyone is welcome and encouraged to attend.