Krausz-Partition

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Der Graph K1,3

Eine Krausz-Partition, benannt nach dem ungarischen Mathematiker József Krausz († 1944), ist in der Graphentheorie eine Menge K von Teilgraphen eines Graphen G = (V,E) mit den folgenden Eigenschaften:

  • Jedes Element von K ist ein vollständiger Graph.
  • Jede Kante e \in E ist in genau einem Element von K enthalten.
  • Jeder Knoten v \in V ist in genau zwei Elementen von K enthalten.

Beineke, Krausz, van Rooij und Wilf konnten in den 1960ern zeigen, dass folgende Aussagen äquivalent sind:

  • L(G) ist Kantengraph zu einem Graphen G.
  • L(G) besitzt eine Krausz-Partition.

Das heißt, es existiert genau dann ein Urbild G eines Kantengraphen L(G), wenn L(G) Krausz-partitionierbar ist.

Der Graph K_{1,3} ist zum Beispiel nicht Krausz-partitionierbar und ist daher auch kein Kantengraph L(G) zu einem beliebigen Graphen G.

Literatur[Bearbeiten]

  •  József Krausz: Démonstration nouvelle d’une théorème de Whitney sur les réseaux. In: Matematikai és Fizikai Lapok. 50, 1943, S. 75–85.