Determining Graph Automorphisms by Determining Ways of Permuting Edges

74 Views Asked by At

Here is an example from the book Groups, Graphs, and Trees (Ignore example 1.15; I accidently included it in my snippet of the pdf):

enter image description here

From my understanding, the symmetry group of a graph $\Gamma$ consists of all bijections $f : V(\Gamma) \to V(\Gamma)$ such that $v,w$ are adjacent vertices if and only if $f(v),f(w)$ are adjacent vertices. So, to construct the symmetry group $Sym(\Gamma)$, we just need to look at the ways which we can map vertices to vertices in such a way that adjacency is preserved.

However, in this example, the author is merely looking at the ways to permute the edges. Strictly speaking, elements in $Sym(\Gamma)$ don't act on edges. Is there another notion of symmetry ("edge" symmetry) which corresponds to the usual symmetry ("vertex" symmetry)? Correspond to in the sense that the "edge" symmetry group is isomorphic to the "vertex" symmetry group?

1

There are 1 best solutions below

9
On BEST ANSWER

Looks like authors call graph what is usually called multigraph with non-labeled edges - they allow existence of multiple edges connecting the same pair of vertices. For such graphs automorphishm is a function acting on both vertices and edges that preserves incidence.