1
$\begingroup$

This question referes to a definition in Eugene M. Luks paper "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time" (1981), page 48, available at http://ix.cs.uoregon.edu/~luks/iso.pdf‎.

Let $X$ be a (simple, undirected) trivalent graph (that is, a graph with max node degree 3) and let $e$ be a distinguished edge in $X$. For $r \in \{1,...,n\}$, let $X_r$ be the subgraph consisting of all vertices and all edges of $X$ which appear in paths of length $\leq{}r$ trough $e$. Let $\text{Aut}_e(X_r)$ be the subgroup of $\text{Aut}(X_r)$ containing all automorphism that fix edge $e$.

It is claimed without proof that $\pi_r: \text{Aut}_e(X_{r+1}) \to \text{Aut}_e(X_r)$, $\sigma \mapsto \sigma|_{X_r}$ (i.e, every automorphism on $X_{r+1}$ is restricted to $X_r$) is a group homomorphism.

However, I do not see how the restriction of any $\sigma\in\text{Aut}_e(X_{r+1})$ is a automorphism on $X_r$ and thus a member of $\text{Aut}_e(X_r)$. Moreover, I think I found a counterexample:

Let $X$ be the fully connected graph with three vertices $v_0,v_1,v_2$. Let the distinguished edge $e=(v_0,v_1)$. Then $X_1$ is the graph with nodes $v_0,v_1$ and edge $e$. $X_2 =X$. Therefore, $\text{Aut}_e(X_1)$ is isomorphic to $S_2$ (containing two elements, the identity and the transposition of both nodes). The automorphism group of $X_2$ however is isomorphic to $S_3$, which also contains the rotation of the nodes. Thus, let $\sigma$ be the rotation $v_i \mapsto v_{i+1}$ with addition modulo 3. Then, for the restriction of $\sigma$ to $X_1$ it holds $\sigma|_{X_1}(v_2) = v_3 \notin X_1$, and therefore $\sigma|_{X_1} \notin \text{Aut}_e(X_1)$. Thus, $\pi_2$ cannot be a group homomorphism $\text{Aut}_e(X_{2}) \to \text{Aut}_e(X_1)$.

I suppose I am missing something. What is it?

$\endgroup$
  • 2
    $\begingroup$ An answer would be: The counterexample given (ie. the rotation) is not an element of $\text{Aut}_e(X_{r+1})$, because it doesn't fix edge $e$. It is therefore not a counterexample. However, I need to wait 8 hours before I can post an answer to my own question. $\endgroup$ – Nils Wisiol Dec 2 '13 at 17:21
1
$\begingroup$

Any graph automorphism must map paths to paths. This can be seen by induction.

Use the definition of a graph homomorphism as the base case (that is, $x\sim y \Rightarrow \psi(x)\sim \psi(y)$). Now assume that $x_1x_2\ldots x_nx_{n+1}$ is a path of length $n+1$. Then $x_1x_2\ldots x_n$ is a path of length $n$, so by inductive hypothesis, $\psi(x_1)\psi(x_2)\ldots \psi(x_n)$ is a path. Now, since $x_n\sim x_{n+1}$, we have $\psi(x_n)\sim \psi(x_{n+1})$, so we have that $\psi(x_1)\psi(x_2)\ldots \psi(x_n)\psi(x_{n+1})$ is a path.

In particular, paths of length at most $n$ are mapped to paths of length at most $n$. Therefore, if $\psi$ is any automorphism of a graph $\Gamma$ containing $X_r$ such that $\psi(e)=e$, we have that $\psi(X_r)\subseteq X_r$, and because $\psi$ is bijective, this means that $\psi(X_r)= X_r$. So, $\psi_{X_r}\in \operatorname{Aut}_e(X_r)$.

Using the same technique, it's easy to see that given two graph automorphisms $\psi$ and $\phi$ fixing $e$, $\psi\phi$ behaves the same in $X_r$ as it does in $\Gamma$. So the restriction map preserves the group structure.

$\endgroup$
0
$\begingroup$

The counterexample given (ie. the rotation) is not an element of $\text{Aut}_e(X_{r+1})$, because it doesn't fix edge $e$. It is therefore not a counterexample.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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