5
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – verret
    Jan 5, 2015 at 8:03

1 Answer 1

6
$\begingroup$

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)$.

Cayley graphs are not a good place to look, because the stabilizer of a vertex tends to consist of automorphisms of the underlying group, and any automorphism that fixes each element in a connection set is the identity.

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ Jan 5, 2015 at 14:28
  • $\begingroup$ The $k>3$ was a typo, which I've fixed. Thanks. $\endgroup$ Jan 5, 2015 at 17:59
  • $\begingroup$ @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. $\endgroup$
    – verret
    Jan 6, 2015 at 1:09
  • $\begingroup$ @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$. $\endgroup$ Jan 6, 2015 at 1:23
  • $\begingroup$ Thanks Chris. By the way, Ashwin, since you asked for it, here is a specific example with L_v of order 3. It is a 4-valent 2-arc-transitive graph of order 32. The vertex-stabiliser has order 72: jan.ucc.nau.edu/swilson/C4Site/N032/N032i005/Forms.html $\endgroup$
    – verret
    Jan 6, 2015 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.