Odd automorphisms in graphs

An automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this talk, I will present the formula for the number of non-isomorphic graphs of order n admitting an odd automorphism, together with some asymptotic estimates. We will then focus on the existence of odd automorphisms in the class of vertex-transitive graphs. A positive integer n is a Cayley number if every vertex-transitive graph of order n is a Cayley graph. By analogy, a positive integer n is said to be a vertex-transitive-odd number (in short, a VTO-number) if every vertex-transitive graph of order n admits an odd automorphism. We will prove that Cayley numbers congruent to 2 modulo 4, cube-free nilpotent Cayley numbers congruent to 3 modulo 4, and numbers of the form 2p, for p a prime, are VTO numbers. At the other extreme, it is possible that the complete graph K_n is the only connected vertex-transitive graph of order n>2 admitting an odd automorphism. We will prove that this happens if and only if n is a Fermat prime. 

This is joint work with Klavdija Kutnar and Dragan Marušič.