Direkt zum Inhalt

Lexikon der Mathematik: Automorphismus eines Graphen

bijektive Abbildung der Eckenmenge eines Graphen auf sich selbst.

Ist G ein Graph mit der Eckenmenge E(G), so nennt man eine bijektive Abbildung f : E(G) → E(G) Automorphismus des Graphen G, wenn für alle x,yE(G) folgendes gilt:

\begin{eqnarray}xy\in K(G)\iff f(x)f(y)\in K(G).\end{eqnarray}

Damit ist ein Automorphismus eines Graphen G ein Isomorphismus von G auf sich selbst. Die Automorphismen von G bilden bezüglich der Hinter- einanderausführung von Abbildungen eine Gruppe, die sogenannte Automorphismengruppe von G, die wir hier mit A(G) bezeichnen. Damit ist A(G) für jeden Graphen G eine Permutationsgruppe auf E(G), und die Automorphismengruppe des vollständigen Graphen Kn ist die symmetrische Gruppe Sn der Ordnung n!.

Natürlich liefern isomorphe Graphen auch isomorphe Automorphismengruppen, aber es existieren auch nicht-isomorphe Graphen mit isomorphen Automorphismengruppen. Es gilt z. B.\(A(G)=A(\bar{G})\), wobei G der Komplementärgraph von G ist. Darüber hinaus lassen sich unendlich viele nichtisomorphe Graphen konstruieren, die isomorphe Automorphismengruppen besitzen.

Man kann beweisen, daß die Ordnung |A(G)| der Automorphismengruppe eines Graphen G mit n Ecken ein Teiler von n! ist, und genau dann |A(G)| = n! gilt, wenn

\begin{eqnarray}G\tilde{=}{K}_{n}\text{oder}\bar{G}\cong {K}_{n}.\end{eqnarray}

Ein Graph G heißt eckentransitiv, wenn für je zwei Ecken u und \(\upsilon \) ein Automorphismus h in A(G) mit \(h(u)=\upsilon \) existiert. Natürlich ist jeder eckentransitive Graph auch regulär. Jedoch zeigt der skizzierte 3-reguläre Graph H, daß die Umkehrung im allgemeinen nicht gilt. Denn betrachtet man z. B. die beiden Ecken x und y, so gibt es keinen Automorphismus von H, der die Ecke x in die Ecke y überführt.

Abbildung 1 zum Lexikonartikel Automorphismus eines Graphen
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Dagegen sind der vollständige Graph Kn, der vollständige bipartite Graph Kn,n und der PetersenGraph Beispiele von eckentransitiven Graphen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos