12. Decompositions and Cutsets
Society for Industrial and Applied Mathematics eBooks · 1999
In this chapter we discuss methods of decomposing a graph into subgraphs. We divide the decompositions into two groups, depending on whether the decomposition splits a graph into connected components by removing a subset of vertices. Decompositions that reduce the size of the graph without removing specific cutsets are considered first. 12.1 Modular decomposition—the poset aspect The modular, substitution, or lexicographic decomposition of graphs and partial orders arose in connection with Gallai's results investigating the structure and recognition of comparability graphs [416] (see also [939, 941, 494, 271, 270, 269, 650, 1084, 971, 552]). The substitution-decomposition theory is by now a well-understood theory with many applications in discrete mathematics. There are, e.g., substitution decompositions for Boolean functions, set systems, and relations. For survey articles see the papers of Möhring [786, 788] and Möhring and Radermacher [791]. We describe here very briefly the substitution decomposition for partial orders and graphs following Möhring [788]. Definition 12.1.1 Let be a partial order, let be pairwise-distinct elements from , and let , be partial orders with mutually disjoint ground sets , . Then is the partial order resulting from substituting the elements of Q with the associated partial order , , such that V= ( V′ / { a1 ,… , ah } )∪ V1 ∪⋯∪ Vh and if and only if there is an i with and or there are i, j, , with , and . The substitution is proper if for some i.