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?

Improve this question
$\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
    Commented Jan 5, 2015 at 8:03

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Ashwin Ganesan
    Commented Jan 5, 2015 at 14:28
  • $\begingroup$ The $k>3$ was a typo, which I've fixed. Thanks. $\endgroup$
    – Chris Godsil
    Commented 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
    Commented 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$
    – Chris Godsil
    Commented 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
    Commented Jan 6, 2015 at 1:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .