Asymmetric graphs

From MaRDI portal





\(G\) (=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 \(+\infty\) festgesetzt. Ferner wird definiert \(A(n) = \text{Max} A[G]\) aller \(G\) mit der (festen) Eckenzahl \(n\). Unter anderem werden folgende Sätze bewiesen: 1. \(A(n) \leq [{1 \over 2} (n-1)]\). 2. Die Wahrscheinlichkeit, unter den \(G\) mit \(n\) Ecken ein \(A[G]/n<{1 \over 2}-\varepsilon\) anzutreffen, konvergiert für jedes (für alle \(n\) gemeinsam gewähltes) \(\varepsilon > 0\) mit \(n \to \infty\) nach 0. 3. \(\lim_{n \to \infty} {A(n) \over n} = {1 \over 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 \over 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 \over 2} (n-1)\), oder auch stärker, daß alle \(\Delta\)-Graphen symmetrisch sind.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Asymmetric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5728982)