For a permutation of a finite set $X$, define its supporting set as the complement in $X$ of its fixed-point set. The term support describes the size of a supporting set. For example, a $k$-cycle has support $k$.
Consider a subgroup $H$ of $S_n$, such as $H=Aut(G)$ for an $n$-vertex graph $G$. We are interested in small generating sets of $H$. But rather than count the generators, we are going to add up their supports and call the result the total support of a generating set.
$H$ can always be generated by at most $n-1$ generators. An elegant proof, anyone?
Is it true that a generating set of $H$ exists with $O(n)$ total support ? If not, an example of the form $Aut(G)$ would be most useful. If yes, can total support be limited by $Cn$ for a known $C>0$ ?
Same question with at most $n-1$ generators.
As an illustration, take $S_n$. It can be generated by $n-1$ transpositions whose total support is $2n-2$. Or by one transposition and a full cycle, whose total support is $n+2$.