Clarifying the concept of symmetry group of a graph

The following self-contained post clarifies the definition of symmetry group of a graph (definition 1.14, p. 10-11, and example 1.15, p. 11, in the book “Groups, graphs and trees: an introduction to the geometry of infinite groups” by John H. Meier).

The symmetry group of a graph, also referred to as the automorphism group of a graph, is informally the set of all possible rearrangements of the graph that preserve its edge-vertex connectivity.

A practical way of understanding what rearrangements are permitted by the symmetry group of a graph is to assign labels to the vertices and edges of the graph. Consider moving around the vertices and edges of the graph in such way so that each graph resulting from the reconfiguration connects the same labelled vertices via the same labelled edges.

For example, the figure below displays a graph \Gamma with labelled vertices \{v_1, v_2, v_3, v_4\} and edges \{e_1, e_2, e_3, e_4, e_5, e_6\}:

group_symmetry_of_graph_original

Six symmetries come from permuting the edges \{e_4, e_5, e_6\} connecting the vertices \{v_1, v_4\} and one symmetry comes from reflecting through a horizontal axis. The symmetry arising from a reflection through the horizontal axis is shown below:

group_symmetry_of_graph_reflected

On the other hand, the graph below does not belong to the symmetry group of the initial graph \Gamma because of connecting v_2 with v_4 through e_2, which introduces a connection not present in \Gamma:

group_symmetry_of_graph_wrong

Let’s count the graphs in the symmetry group of \Gamma. Six graphs symmetric to \Gamma arise from permuting the edges \{e_4, e_5, e_6\}, and this set of six graphs is isomorphic to the symmetric group \mbox{Sym}_3. The original graph \Gamma along with its reflection through the horizontal axis gives a set of two graphs isomorphic to \mbox{Sym}_2. So the symmetry group of \Gamma contains 6\times 2 =12 graphs, and is isomorphic to the direct product \mbox{Sym}_3\bigoplus\mbox{Sym}_2.

The main aim of this blog post is to provide a mathematically rigorous definition of the symmetry group of a graph starting by the concept of graph symmetry. A symmetry of a graph \Gamma=(V,E) with vertex set V and edge set E is a permutation f of the vertex set V such that the pair of vertices \{v_1,v_2\} form an edge in \Gamma if and only if the pair \{f(v_1), f(v_2)\} also form an edge in \Gamma.

Unfortunately, there is an error in this first definition. In the previous example, if the edges e_4 and e_5 are permuted, a new distinct graph from the symmetry group of \Gamma arises, which is not accounted by the definition due to permuting the edges but not the vertices of \Gamma.

A more mathematically accurate definition is provided in John Meier’s book “Groups, graphs and trees: an introduction to the geometry of infinite groups” (definition 1.14, p. 10-11). According to Meier’s definition, a symmetry of a graph \Gamma with vertices V(\Gamma) and edges E(\Gamma) is a bijection f taking vertices to vertices and edges to edges such that if \mbox{ends}(e)=\{v_1,v_2\} in \Gamma, then \mbox{ends}(f(e))=\{f(v_1),f(v_2)\} in \Gamma, where \mbox{ends}(e)=\{v_1,v_2\} denotes the set of two vertices v_1 and v_2 connected by an edge e.

Meier’s definition corrects the issue of the previous definition, but does not tell what is the domain and range of f. In fact, trying to define the domain and range of f does not seem to be obvious due to the dubious notation f(e) and f(v_1).

One possible way round this problem is to define graph symmetry to be a set of two separate bijections, one on the vertices and one on the edges of the graph. The third definition would take the following form; a symmetry of a graph \Gamma with vertices V(\Gamma) and edges E(\Gamma) is a set \{f_1,f_2\} of bijections f_1:V(\Gamma)\rightarrow V(\Gamma) and f_2:E(\Gamma)\rightarrow E(\Gamma) such that if \mbox{ends}(e)=\{v_1,v_2\} in \Gamma, then \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\} in \Gamma.

Note that the converse holds in the above definition, i.e. \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\} in \Gamma\Rightarrow\mbox{ends}(e)=\{v_1,v_2\} in \Gamma. To prove this, assume that \mbox{ends}(e)=\{q,r\}\ne \{v_1,v_2\}. From the definition, \mbox{ends}(e)=\{q,r\}\Rightarrow\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}. Given that \{q,r\}\ne \{v_1,v_2\}, assume without loss of generality that q\ne v_1 and q\ne v_2. Since f_1 is a bijection, it follows that f_1(q)\ne f_1(v_1) and f_1(q)\ne f_1(v_2), which is a contradiction since the edge f_2(e) connects two vertices according to \{f_1(v_1),f_1(v_2)\}=\mbox{ends}(f_2(e))=\{f_1(q),f_1(r)\}.

In light of the validity of the inverse, one can define graph symmetry using the equivalence \mbox{ends}(e)=\{v_1,v_2\} in \Gamma\iff \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\} in \Gamma.

However, this third definition raises one more question. Having two separate bijections, one for vertices and one for edges, does not allow to define graph symmetry as a single function. The solution is to define a symmetry f of a graph \Gamma by f(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}.

So the third definition can now be corrected. A symmetry of a graph \Gamma with vertices V(\Gamma) and edges E(\Gamma) is a bijection f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma) defined byf(x)= \begin{cases} f_1(x) \mbox{ if } x\in V(\Gamma)\\ f_2(x)\mbox{ if } x\in E(\Gamma)\end{cases}, where f_1:V(\Gamma)\rightarrow V(\Gamma) and f_2:E(\Gamma)\rightarrow E(\Gamma) are two bijections such that if \mbox{ends}(e)=\{v_1,v_2\} in \Gamma, then \mbox{ends}(f_2(e))=\{f_1(v_1),f_1(v_2)\} in \Gamma.

This corrected third definition coincides with Meier’s definition if the latter is clarified formally as follows; a symmetry of a graph \Gamma with vertices V(\Gamma) and edges E(\Gamma) is a bijection f:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma) with the following three properties:

  • v\in V(\Gamma)\Rightarrow f(v)\in V(\Gamma),
  • e\in E(\Gamma)\Rightarrow f(e)\in E(\Gamma),
  • \mbox{ends}(e)=\{v_1,v_2\} in \Gamma\Rightarrow\mbox{ends}(f(e))=\{f(v_1),f(v_2)\} in \Gamma.

Having defined graph symmetry, the symmetry group of a graph becomes simply the collection of all graph symmetries. Formally, the symmetry group \mbox{Sym}(\Gamma) of a graph \Gamma is the set of symmetries of \Gamma equipped with the operation of composition of graph symmetries.

Note that the composition f\circ g of two graph symmetriesf:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma) andg:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma) is essentially a composition of two vertex or edge permutations.

One thought on “Clarifying the concept of symmetry group of a graph

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s