Direkt zum Inhalt

Lexikon der Mathematik: Krausz, Satz von

gibt eine notwendige und hinreichende Bedingung dafür, daß ein gegebener Graph der Kantengraph eines anderen Graphen ist.

Präzise formuliert hat J.Krausz im Jahre 1943 folgenden Charakterisierungssatz bewiesen.

Ein Graph G ist genau dann der Kantengraph eines Graphen H, also G ≅ L(H), wenn sich G in kantendisjunkte Cliquen S1, S2, …, Sq so zerlegen läßt, daß jede Ecke von G zu höchstens zwei dieser Cliquen gehört.

Besitzt G eine solche Cliquenzerlegung S1, S2, …, Sq, so läßt sich der Graph H wie folgt konstruieren. Ist UE(G) die Menge aller Ecken, die in genau einer Clique Si für i = 1, 2, …, q liegen, so besteht E(H) aus U und der Menge S = { S1, S2, …, Sq}. Die Kantenmenge von H setzt sich aus der Vereinigung der beiden Mengen \begin{eqnarray}{K}_{1}(H)=\{{S}_{i}{S}_{j}|E({S}_{i})\cap E({S}_{j})\ne 0,i\ne j\}\end{eqnarray}

und \begin{eqnarray}{K}_{2}(H)=\{x{S}_{i}|x\in U\text{und}x\in E({S}_{i})\}\end{eqnarray}

zusammen.

Eine weitere wichtige Charakterisierung der Kantengraphen gelang L.W. Beineke 1968 durch 9 verbotene induzierte Teilgraphen, und 1994 reduzierte L. Soltés die Anzahl dieser verbotenen induzierten Teilgraphen auf 7, falls der Graph mindestens 9 Ecken besitzt.

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