# Structure of the stabilizer of a vertex-neighborhood of a vertex-transitive graph

Given a simple, undirected graph and a vertex $v$ of the graph, let $L_v$ denote the set of automorphisms of the graph that fixes the vertex $v$ and each of its neighbors. When the graph is vertex-transitive, the vertex-neighborhood stabilizer $L_v$ is independent of the choice of $v$.

I noticed that for many vertex-transitive graphs, $L_v$ happens to be either trivial or is isomorphic to the direct product of copies of $C_2$. Thus $L_v$ happens to be isomorphic to $C_2^k$ for some $k \ge 0$. For example, for the modified bubble-sort graph on 24 vertices, $L_v$ is the Klein four-group $C_2 \times C_2$, and for many Cayley graphs generated by transposition sets, $L_v$ is trivial (so $k=0$ in this case) (cf. http://arxiv.org/abs/1205.5199). For the complete transposition graph, $L_v \cong C_2$ (cf. http://arxiv.org/abs/1404.7363). I also considered the Petersen graph, and again $L_v \cong C_2$. Is this a coincidence or is there some result that says that for some families of vertex-transitive graphs or for certain families of Cayley graphs, $L_v \cong C_2^k$ for some $k$? What are some counterexamples - for example, what are some (vertex-transitive) graphs for which $L_v \cong C_3$, say?

• Let $\Gamma$ be a vertex-transitive graph and consider the lexicographic product of $\Gamma$ with an edgeless graph of order $k$. In this case, $L_v$ will contain a copy of $(Sym_k)^n$ where $n$ is the number of vertices in $\Gamma$ at distance at least $2$ from a given vertex. – verret Jan 5 '15 at 8:03

Consider the Kneser graph $K(v,k)$, with vertices the $k$-subsets of $V=\{1,\ldots,v\}$, where the $k$-subsets are adjacent if they are disjoint. Let $\alpha=\{1,\ldots,k\}$ and let $G$ be the subgroup of the symmetric group on $V$ that fixes each element of the complement of $\alpha$. So $|G|=k!$ and $G$ is a subgroup of the stablizer of $\alpha$ that fixes each neighbour of $\alpha$ in the Kneser graph.
To get examples as you requested, take $k\ge 3$ (and $v>2k)$.
• The Kneser graphs $K(v,k)$ work; $k=3$ also works. Regarding Cayley graphs, it is possible that an automorphism that fixes each element in the connection set is nontrivial, as in the examples mentioned above. This happens if the Cayley graph is not normal, and I was wondering if there are examples of such cases where $L_v$ (when it is nontrivial) is not isomorphic to $C_2$. – Ashwin Ganesan Jan 5 '15 at 14:28
• The $k>3$ was a typo, which I've fixed. Thanks. – Chris Godsil Jan 5 '15 at 17:59
• @Ashwin, You are correct that Chris was referring to "normal" Cayley graphs with the comment at the end of his answer. While it is likely that, in some sense, "most" Cayley graphs are normal (which is why he said "tends to"), there are still plenty of Cayley examples to your question. In fact, if I remember correctly, for any starting vertex-transitive graph $\Gamma$, there are infinitely many values of $k$ for which the construction in my previous comment will yield a Cayely graph. – verret Jan 6 '15 at 1:09
• @verret: If $X$ is a vertex-transitive graph and the stabilizer of a vertex has order $m$, then the lexicographic product of the empty graph on $m$ vertices by $X$ is Cayley. So your construction is Cayley whenever $m$ divides $k$. – Chris Godsil Jan 6 '15 at 1:23