Relation between Automorphism group of a graph and its subgraph

Question

Let $G$ be a graph on $r$ vertices $\{1,2,\ldots,r\}$. Further denote $H$ to be the sub-graph of $G$ induced by the vertices $\{1,2,\ldots,(r-1)\}$. Denote $Aut(G)$ and $Aut(H)$ to be the automorphism group of graphs $G$ and $H$ respectively. Is it true that $$ |Aut(G)| \le r |Aut(H)|, $$ or even $$ |Aut(G)| \le C r |Aut(H)|, $$ for some universal constant $C$?

Answer 1

The answer to your first question is yes, this follows from the orbit-stabiliser theorem. If H is the subgraph obtained by removing the vertex $v$, then $Aut(H)$ will contain a copy of the vertex-stabiliser $Aut(G)_v$ (although it may be bigger). By the orbit-stabiliser theorem, $|Aut(G):Aut(G)_v|\leq r$ and the result follows.

Answer 2

Take $X$ to be a Paley graph on $q$ vertices. Then $|\mathrm{Aut}(X)\ge q(q-1)/4$. But $X$ contains, as induced subgraphs, all finite graphs on something like $\log(q)$ vertices (Bollobas and Thomason); in particular it has asymmetric subgraphs of this order.

For another family of examples take a group $G$ which admits a Cayley graph $X$ such that $\mathrm{Aut}(X)\cong G$. (A so-called graphical representation of $G$, aka GRR.) Then the subgraph of $X$ we get by deleting a vertex is asymmetric. Finite groups of order greater than 32 that are not abelian with exponent greater than two, or generalized dicyclic, always have a GRR.