0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ In the field of geometric group theory, one typically refers to any one-dimensional CW complex as just a graph, and refers to graphs where every edge corresponds uniquely to a pair of distinct vertices as a simple or simplicial graph. $\endgroup$ – Rylee Lyman Apr 23 at 0:24
  • $\begingroup$ So, as a function what is the domain/codomain of a graph automorphism $f$? It can't just be $V(\Gamma)$. Is it $V(\Gamma) \cup E(\Gamma)$, with the stipulation that $f(V(\Gamma)) \subseteq V(\Gamma)$ and $f(E(\Gamma)) \subseteq E(\Gamma)$? $\endgroup$ – user193319 Apr 23 at 10:00
  • $\begingroup$ Yes, it is defined on $V \cup E$, such that $F(V) = V$, $F(E) = E$ and if $\langle x, y\rangle \in E$ then $f(\langle x, y\rangle) = \langle f(x), f(y)\rangle$. $\endgroup$ – mihaild Apr 23 at 11:12
  • $\begingroup$ @mihaild I'm still a little confused. Why does it suffice to keep the vertices fixed and just look at the ways of rearranging the edges in order to determine $Sym(\Gamma)$? $\endgroup$ – user193319 Apr 23 at 21:06
  • $\begingroup$ It's not. But in this case group of automorphisms is direct product of it's two subgroups, one of which keeps vertices fixed (and the other keeps most edges fixed). $\endgroup$ – mihaild Apr 23 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.