3
$\begingroup$

Suppose we have two automorphisms on a graph $G$ such that each one swaps a separate pairs of vertices. Is it possible to construct (or prove the existence of) a third automorphism that swaps both pairs simultaneously? More specifically, let $A$ and $B$ be two automorphisms on $G$ and let $x$, $y$, $z$, $w$ be four distinct nodes in the graph, such that

$$A ~~\text{swaps}~~ x ~~\text{and}~~ y\text{, i.e.}~~ A(x) = y ~~\text{and}~~ A(y) = x$$

and

$$B ~~\text{swap}~~ w ~~\text{and}~~ z\text{, i.e.}~~ B(w) = z ~~\text{and}~~ B(z) = w$$

The question that I'm trying to solve is whether there exists an automorphism $C$ such that $C$ swaps both $x$, $y$ and $w$, $z$ i.e.

$$C(x) = y ~~\text{and}~~ C(y) = x ~~\text{and}~~ C(w) = z ~~\text{and}~~ C(z) = w$$

So far my attempts failed (probably because my graph theory background is not that strong). May be the answer is straightforward so apologies if this doesn't qualify as a "research level" question. Any pointers would be highly appreciated. Thanks.

$\endgroup$

1 Answer 1

8
$\begingroup$

Label the vertices of $C_5$ cyclically: $x,y,z,w,v$. There is a (unique) automorphism that swaps $x$ and $y$, and another (unique) automorphism that swaps $z$ and $w$, but there is no automorphism that swaps both pairs.

$\endgroup$
1
  • $\begingroup$ Of course, a counter example is a good idea and I should've thought about that :) Thanks. $\endgroup$
    – Francis K
    Nov 14, 2014 at 6:35

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.