The topic of the talk will be finite connected graphs admitting an automorphism group that acts transitively on the arcs of the graph. These graphs are traditionally called symmetric. The main theme of this talk is the following question:

How many automorphisms can a symmetric graph of order $n$ have?

For $n\geq 3$, the number of automorphisms of a symmetric graph on $n$ verticesis at least $2n$ and at most $n!$. (These values are sharp, as witnessed by cycles and complete graphs.)

The story becomes more interesting if one fixes the valence. Clearly, the number of automorphisms of a symmetric graphof valence $k$ and order $n$ is at least $kn$ (since $kn$ is the number of arcs), and at most $nk\sqrt{(k-1)!}^{\,n-1}$ (as can be shown without much trouble).

While this upper bound is quite good for some values of $k$, it is very far frombeing sharp for some others. For example, for every even $n$ at least $6$,one can construct a $4$-valent symmetric graph of order $n$ with $n\sqrt{2}^n$ automorphisms,showing that the above bound is “almost sharp” for $k=4$. Similar examples can be constructed for any composite $k$.

On the other hand, a classical result of Tutte says that a $3$-valent symmetric graph of order $n$ can have at most $48n$ automorphisms, and a similar linear bound can be proved for any prime value of $k$.

The question: “under what circumstances the order of the automorphism group of a symmetric graph canbe bounded by a linear function of the order of the graph?” is related to several classical problems, like the Sims conjecture on primitive groups,the Weiss conjecture on locally primitive graphs, or the Praeger conjecture on locally quasiprimitive graphs.

On the other hand, not much work has been done on determining which classes of symmetric graphs admit a polynomial (or even sub-exponential) bound on the order of their automorphism groups. Some recent results along these lines will be presented in the talk.