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,y ∈ E(G) folgendes gilt:
\begin{eqnarray}xy\in K(G)\iff f(x)f(y)\in K(G).\end{eqnarray}
Damit ist ein Automorphismus eines GraphenG 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.
Dagegen sind der vollständige Graph Kn, der vollständige bipartite GraphKn,n und der PetersenGraph Beispiele von eckentransitiven Graphen.
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.