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.

Improve this question
$\endgroup$

1 Answer 1

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

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

You must log in to answer this question.

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