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 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 K_n ist die symmetrische Gruppe S_n 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 K_n, der vollständige bipartite Graph K_n,n und der PetersenGraph Beispiele von eckentransitiven Graphen.