ungerichteter, schlingen- und doppelkantenfreier Graph) heißt symmetrisch, wenn es einen nicht-identischen Automorphismus von G gibt. Verff. führen ein "Maß" für die Asymmetrie von Graphen ein. Die kleinste Summe r+s, mit der es durch Wegnahme von r Kanten und Adjunktion von s (neuen) Kanten gelingt, G in einen symmetrischen Graphen zu verwandeln, heißt der Asymmetriegrad A[G] von G. Der Asymmetriegrad des aus einer Ecke bestehenden Graphen wird mit +oo festgesetzt. Ferner wird definiert A(n) = Max A[G] aller G mit der (festen) Eckenzahl n. Unter anderem werden folgende Sätze bewiesen: 1. A(n) \leq [ 1/2 (n-1)]. 2. Die Wahrscheinlichkeit, unter den G mit n Ecken ein A[G]/n < 1/2 -\epsilon anzutreffen, konvergiert für jedes (für alle n gemeinsam gewähltes) \epsilon > 0 mit n ––> oo nach 0. 3. limn ––> oo {A(n) \over n} = 1/2 (folgt aus (1) und (2)). 4. Die Wahrscheinlichkeit, unter den abzählbar unendlichen Graphen einen symmetrischen Graphen zu treffen, ist gleich 1.
Endliche und abzählbar unendliche Graphen verhalten sich also entgegengesetzt, so daß die "meisten" endlichen Graphen asymmetrisch (d.h. nicht symmetrisch), die "meisten" unendlichen Graphen dagegen symmetrisch sind. Von Interesse sind noch mehrere im Text gestellte, offen gebliebene Fragen über den Asymmetriegrad. Zum Beispiel zeigt der Beweis von (1), daß die obere Schranke in (1) auch bei Einschränkung auf diejenigen Automorphismen respektiert wird, bei denen (nur) zwei Ecken in G vertauscht werden. Ist bei dieser Einschränkung der Automorphismen von G das Min. von r+s gleich 1/2 (n-1), so heißt G ein \Delta-Graph. Es wird von den Verff. vermutet, daß es keinen Graphen G gibt mit A[G] = 1/2 (n-1), oder auch stärker, daß alle \Delta-Graphen symmetrisch sind.
Reviewer: K.Wagner
Classif.: * 05C99 Graph theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag
