Graph with distinct automorphisms but no fixed-point free automorphism

148 Views Asked by At

Does there exist a graph $G = \{ V, E \}$ with the following properties:

  • for every node $v_i \in V$ there is an automorphism $\varphi$ for which $\varphi(v_i) \neq v_i$
  • $G$ has no fixed-point-free automorphism (i.e. an automorphism $\varphi'$ in which for all $i$ $\varphi'(v_i) \neq v_i$)

If the answer is yes is there a small example?

2

There are 2 best solutions below

0
On BEST ANSWER

... this seems a good example: at least one automorphism for each vertex such that $\varphi(v_i) \neq v_i$, but no FPF automorphism:

Counterexample 9FCDB7A13F73E9B27A8802D33AFDEA09

9
On

The answer is no, it always has a FPF automorphism and therefore, GI is polynomial equivalent to FPF automorphism (a NP complete problem). In fact, I have 2 distinct proofs to the statement above.