Krausz partition
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:
- Each element of is a complete graph .
- Each edge is contained in exactly one element of .
- Each node is contained in at most two elements of .
Beinke, Krausz, van Rooij and Wilf were able to show in the 1960s that the following statements are equivalent:
- is an edge graph to a graph .
- has a Krausz partition .
That means, there exists an archetype of an edge graph if and only if Krausz is partitionable .
For example, the graph is not Krausz-partitionable and is therefore not an edge graph for any graph .
example
Let be the following graph. As described above, this should be partitioned into complete subgraphs with the desired properties.
By trial and error or with the Roussopoulos algorithm, the following partitioning can be found:
With the Krausz partition the underlying original graph can be constructed as follows :
- The set of nodes results from :
- is the set of complete subgraphs of the Krausz partition just determined, so . In this example is therefore .
- 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 .
- For the edge set of applies to:
- , d. H. two different elements from are connected when they have a common node from . In our example, they are all connected.
- , 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 .
This construction leads to the following archetype:
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] ).