Split (graph theory)

When a cut-set forms a complete bipartite graph, its cut is called a split.

This decomposition can be represented by a tree whose leaves correspond one-to-one with the given graph, and whose edges correspond one-to-one with the strong splits of the graph, such that the partition of leaves formed by removing any edge from the tree is the same as the partition of vertices given by the associated strong split.

The quotient graph can be formed by deleting i from the tree, forming subsets of vertices in G corresponding to the leaves in each of the resulting subtrees, and collapsing each of these vertex sets into a single vertex.

The cut-set of the split is just the single bridge edge, which is a special case of a complete bipartite subgraph.

Similarly, if v is an articulation point of a graph that is not 2-vertex-connected, then the graph has multiple splits in which v and some but not all of the components formed by its deletion are on one side, and the remaining components are on the other side.

Cunningham (1982) already showed that it is possible to find the split decomposition in polynomial time.