Orbits and Stabilizers of Graph Symmetries

From Graph Symmetries to Vertex Sets

A graph automorphism can move vertices while preserving every adjacency relation. Looking at the possible destinations of a vertex gives its orbit; looking at the symmetries that leave it fixed gives its stabilizer. These record two different features: an orbit describes how far a vertex can move under the available symmetries, while a stabilizer describes which symmetries remain when that vertex is held in place.

Throughout, graphs are finite and simple. An automorphism of \(G=(V,E)\) is a bijection \(g:V\to V\) such that \(uv\in E\) if and only if \(g(u)g(v)\in E\). The set of all automorphisms, with composition as its operation, is the automorphism group \(\operatorname{Aut}(G)\). Its identity is the map fixing every vertex, and the inverse of an automorphism is also an automorphism.

An orbit is a set of vertices; a stabilizer is a set of automorphisms. In particular, an automorphism fixing \(v\) need not fix every other vertex. Orbits describe which vertices are interchangeable by symmetries of the whole graph, not merely which vertices have the same degree or look similar locally.

General Facts About Orbits and Stabilizers

Proof. Define \(u\sim v\) when \(g(u)=v\) for some \(g\in\operatorname{Aut}(G)\). The identity automorphism gives \(u\sim u\), so the relation is reflexive. If \(g(u)=v\), then \(g^{-1}(v)=u\), so \(v\sim u\); the relation is symmetric. If \(g(u)=v\) and \(h(v)=w\), then \((hg)(u)=w\), so \(u\sim w\); the relation is transitive. Thus \(\sim\) is an equivalence relation, and its equivalence classes are exactly the orbits. They therefore partition \(V(G)\).

For the stabilizer, the identity fixes \(v\), so it belongs to \(\operatorname{Stab}(v)\). If \(g,h\) fix \(v\), then \((gh)(v)=g(h(v))=g(v)=v\), so \(gh\) fixes \(v\). If \(g(v)=v\), applying \(g^{-1}\) gives \(g^{-1}(v)=v\). Hence the stabilizer contains the identity and is closed under composition and inverses, so it is a subgroup. \(\square\)

A useful way to compute the action is to list the possible automorphisms and apply each one to the chosen vertex. For familiar graphs, the automorphisms have particularly simple forms. The next examples derive the forms needed for the calculations rather than relying on a drawing.

Paths: Reflection Pairs the Vertices

More generally, for \(P_n\) with \(n\ge2\), the only automorphisms are the identity and the reversal \(i\mapsto n+1-i\), by the same endpoint argument. Thus the orbit of \(i\) is \(\{i,n+1-i\}\), with a singleton when \(i=n+1-i\). For odd \(n\), the middle vertex is fixed by both automorphisms; for even \(n\), no vertex is fixed by the reversal. For \(P_1\), there is only the identity automorphism, so its sole vertex forms a singleton orbit and its stabilizer is the whole (trivial) group.

Cycles: Rotations and Reflections

The same calculation works for every cycle \(C_n\), where \(n\ge3\). Rotations \(r_a(i)=i+a\pmod n\) show that every vertex has orbit \(V(C_n)\). A rotation fixes a chosen vertex only if it is the identity. For a chosen vertex \(i\), exactly one reflection, \(s_{2i}(j)=2i-j\pmod n\), fixes it: solving \(a-i=i\pmod n\) gives \(a=2i\pmod n\). Hence its stabilizer consists of the identity and that reflection. This argument includes \(C_3\); its six symmetries are the rotations and reflections described by these same formulas.

The Cube: Coordinate Symmetries

Write a vertex of the cube graph \(Q_3\) as a binary triple \(x=(x_1,x_2,x_3)\), where each \(x_i\) is \(0\) or \(1\). Two vertices are adjacent exactly when they differ in one coordinate. This definition specifies the graph without requiring a picture.

Proof. First, each map of the stated form is a bijection. If two triples differ in exactly one coordinate, permuting their coordinates preserves that property, and adding the same triple \(b\) modulo \(2\) also preserves it. Thus the map preserves adjacency in both directions and is an automorphism.

For the converse, let \(g\) be any automorphism. The distance between two vertices is the length of a shortest path between them. Automorphisms preserve distance: a path maps to a path of the same length, so \(d(g(u),g(v))\le d(u,v)\); applying the same argument to \(g^{-1}\) gives the reverse inequality. Let \(000\) map to \(b\). Its three neighbors are \(100,010,001\), so their images are the three distinct neighbors of \(b\), in some order. This order specifies a permutation \(\pi\) of the three coordinates. The vertices at distance two from \(000\) are \(110,101,011\). Each is the common neighbor other than \(000\) of a particular pair of its neighbors: \(110\) is adjacent to \(100\) and \(010\), \(101\) to \(100\) and \(001\), and \(011\) to \(010\) and \(001\). For each such pair, the other common neighbor is uniquely determined, so the images of all three distance-two vertices are forced by the images of the three neighbors. Finally, \(111\) is the only vertex at distance three from \(000\), so its image is forced as well. The map \(x\mapsto b\mathbin{\oplus}\pi(x)\) has the same image \(b\) for \(000\), the same images of the three neighbors according to the chosen permutation, and preserves distances and adjacency. Since those choices force the image of every vertex, \(g\) is that map. \(\square\)

Common Pitfall: Fixing a Vertex Is Not the Same as Being the Identity

For \(C_6\), it is wrong to conclude that the stabilizer of \(0\) contains only the identity because every nonidentity rotation moves \(0\). The calculation \(s_0(i)=-i\pmod6\) shows that the nonidentity reflection \(s_0\) also fixes \(0\). A stabilizer must be checked against every type of automorphism, not just rotations. More generally, count automorphisms that fix the chosen vertex, rather than assuming that a fixed vertex forces the entire automorphism to be the identity.

The examples show three different patterns: a path may have several vertex orbits, a cycle has one orbit with a reflection in each vertex stabilizer, and the cube has one orbit with coordinate permutations in the stabilizer of \(000\). In each case, the calculation starts by identifying the full set of automorphisms and then applying those maps to vertices.