Krausz-Partition

Krausz-Partition: Der Graph K_1,3

Eine Krausz-Partition 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$ .

Kategorie:
Graphentheorie

Игры ⚽ Поможем написать реферат

Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… … Wikipedia
ENGLAND — The British Isles were unknown to the Jews until a late date, and the settlement of the Jews in medieval England was among the latest in Europe. It is possible that a small nucleus was to be found there under the Romans and that in the Saxon… … Encyclopedia of Judaism
Amazon Women on the Moon — Cheeseburger film sandwich Cheeseburger film sandwich (Amazon Women on the Moon) est un film à sketches écrit par Michael Barrie et Jim Mulholland en 1987. Sommaire 1 Synopsis 2 Fiche technique 3 Sketches 3.1 … Wikipédia en Français
Cheeseburger film sandwich — (Amazon Women on the Moon) est un film à sketches écrit par Michael Barrie et Jim Mulholland en 1987. Sommaire 1 Synopsis 2 Fiche technique 3 Sketches 3.1 Mondo C … Wikipédia en Français

Academic dictionaries and encyclopedias