# Krausz partition

The graph K 1,3

A Krausz partition , named after the Hungarian mathematician József Krausz († 1944), is in graph theory a set of subgraphs of a graph with the following properties: ${\ displaystyle K}$ ${\ displaystyle G = (V, E)}$

• Each element of is a complete graph .${\ displaystyle K}$
• Each edge is contained in exactly one element of .${\ displaystyle e \ in E}$${\ displaystyle K}$
• Each node is contained in at most two elements of .${\ displaystyle v \ in V}$${\ displaystyle K}$

Beinke, Krausz, van Rooij and Wilf were able to show in the 1960s that the following statements are equivalent:

• ${\ displaystyle L (G)}$is an edge graph to a graph .${\ displaystyle G}$
• ${\ displaystyle L (G)}$has a Krausz partition .

That means, there exists an archetype of an edge graph if and only if Krausz is partitionable . ${\ displaystyle G}$ ${\ displaystyle L (G)}$${\ displaystyle L (G)}$

For example, the graph is not Krausz-partitionable and is therefore not an edge graph for any graph . ${\ displaystyle K_ {1,3}}$${\ displaystyle L (G)}$${\ displaystyle G}$

## example

Let be the following graph. As described above, this should be partitioned into complete subgraphs with the desired properties. ${\ displaystyle L (G)}$

A given edge graph

By trial and error or with the Roussopoulos algorithm, the following partitioning can be found:

The complete subgraphs of the Krausz partition.

With the Krausz partition the underlying original graph can be constructed as follows : ${\ displaystyle G = (V, E)}$

• The set of nodes results from : ${\ displaystyle V}$${\ displaystyle S \ cup U}$
• ${\ displaystyle S}$is the set of complete subgraphs of the Krausz partition just determined, so . In this example is therefore .${\ displaystyle S = \ left \ {S_ {1}, S_ {2}, \ dots \ right \}}$${\ displaystyle S = \ left \ {S_ {1}, S_ {2}, S_ {3} \ right \}}$
• ${\ displaystyle U}$is the set of nodes from which are in exactly one of the complete subgraphs from . In this example . The nodes and are each available in exactly two of the complete subgraphs and are therefore not elements of .${\ displaystyle L (G)}$${\ displaystyle S}$${\ displaystyle U = \ left \ {1,3,6 \ right \}}$${\ displaystyle 2,4}$${\ displaystyle 5}$${\ displaystyle S}$${\ displaystyle U}$
• For the edge set of applies to: ${\ displaystyle E}$${\ displaystyle E = E_ {1} \ cup E_ {2}}$
• ${\ displaystyle E_ {1} = \ left \ {S_ {i} S_ {j} \ mid E (S_ {i}) \ cap E (S_ {j}) \ neq \ emptyset, i \ neq j \ right \ }}$, d. H. two different elements from are connected when they have a common node from . In our example, they are all connected.${\ displaystyle S}$${\ displaystyle L (G)}$${\ displaystyle S_ {i}}$
• ${\ displaystyle E_ {2} = \ left \ {xS_ {i} \ mid x \ in U {\ text {and}} x \ in E (S_ {i}) \ right \}}$, d. H. a node from is connected to one if this node is part of the complete subgraph . In our example this leads to the edges and .${\ displaystyle U}$${\ displaystyle S_ {i}}$${\ displaystyle S_ {i}}$${\ displaystyle 1S_ {2}, 3S_ {1}}$${\ displaystyle 6S_ {1}}$

This construction leads to the following archetype:

The underlying original graph.

## literature

• József Krausz: Demonstration nouvelle d'une théorème de Whitney sur les réseaux . In: Matematikai és Fizikai Lapok . tape 50 , 1943, pp. 75-85 .
• Lutz Volkmann: Foundations of the graph theory . Springer, Vienna / New York 1996, ISBN 3-211-82774-9 , pp. 182-183 .
• Nicholas D. Roussopoulos: A max {m, n} algorithm for deterministic mining the graph H from its line graph G . S. 108-112 , doi : 10.1016 / 0020-0190 (73) 90029-X ( [1] ).