Krausz partition

from Wikipedia, the free encyclopedia
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:

  • 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.

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 :

  • 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:

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] ).