5
$\begingroup$

Many connected vertex-transitive graphs $G=(V,E)$ have the property that some of their automorphisms other than the identity have fixed points. To point out two simple examples:

  • If $G = K_3$ then the automorphism swapping the points of an edge and leaving the remaining point intact has $1$ fixed point.
  • For $G = C_4$, the "mirror map" along one of the diagonals has those diagonal points as fixed points.

But for both graphs, there are automorphisms that do not have any fixed points. (For both examples, consider a rotation map.)

Is there a connected vertex-transitive graph $G=(V,E)$ with $|V| \geq 2$ such that every automorphism has a fixed point?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ By the way, not directly related to your question, but the fixed-point property for graphs has apparently been studied by Bernd Schröder in "The Fixed Vertex Property for Graphs" (doi.org/10.1007/s11083-014-9337-5) $\endgroup$
    – Sam Hopkins
    Commented Apr 18, 2022 at 20:29

1 Answer 1

Reset to default
9
$\begingroup$

Let me convert my comments into an answer.

There is no such [EDIT:] finite graph $G$. Indeed, something stronger can be said. Suppose that a group $\Gamma$ acts transitively by permutations on a finite set $X$ , with $\#X \geq 2$. Then there is some $\gamma \in \Gamma$ for which $\gamma\colon X \to X$ has no fixed points. The proof is a simple application of Burnside's Lemma, see e.g. https://math.stackexchange.com/questions/106158/every-transitive-permutation-group-has-a-fixed-point-free-element.

For infinite graphs, see this other question: Infinite vertex-transitive graph where every automorphism has a fixed vertex

Improve this answer
$\endgroup$
9
  • 3
    $\begingroup$ Could there be a vertex-transitive infinite graph with no fixed-point-free automorphism? $\endgroup$
    – bof
    Commented Apr 19, 2022 at 5:32
  • 1
    $\begingroup$ There are infinite transitive permutation groups with no derangements other than the identity, but I don’t know if they can be the full automorphism group of a graph. $\endgroup$
    – Gordon Royle
    Commented Apr 19, 2022 at 10:38
  • 2
    $\begingroup$ @GordonRoyle Of course, the identity is also not a derangement. (And yes it is very easy to find a transitive permutation action on an infinite set with no fixed-point free permutations: e.g. take all permutations which only displace finitely many things.) $\endgroup$
    – Sam Hopkins
    Commented Apr 19, 2022 at 12:37
  • 3
    $\begingroup$ @AgnishomChattopadhyay: but that is about whether the group is abstractly the automorphism group of a graph, which then tells you nothing about fixed points. $\endgroup$
    – Sam Hopkins
    Commented Apr 19, 2022 at 16:14
  • 1
    $\begingroup$ @bof I asked this as a new question here: mathoverflow.net/questions/420668/…. $\endgroup$
    – Sam Hopkins
    Commented Apr 19, 2022 at 18:44

You must log in to answer this question.

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