Clique-sum

Short description: Gluing graphs at complete subgraphs

A clique-sum of two planar graphs and the Wagner graph, forming a K₅-minor-free graph.

In graph theory, a branch of mathematics, a clique sum (or clique-sum) is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges (the original definition, based on the notion of set sum) or possibly deleting some of the clique edges (a loosening of the definition). A k-clique-sum is a clique-sum in which both cliques have exactly (or sometimes, at most) k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

Different sources disagree on which edges should be removed as part of a clique-sum operation. In some contexts, such as the decomposition of chordal graphs or strangulated graphs, no edges should be removed. In other contexts, such as the SPQR-tree decomposition of graphs into their 3-vertex-connected components, all edges should be removed. And in yet other contexts, such as the graph structure theorem for minor-closed families of simple graphs, it is natural to allow the set of removed edges to be specified as part of the operation.

Related concepts

Clique-sums have a close connection with treewidth: If two graphs have treewidth at most k, so does their k-clique-sum. Every tree is the 1-clique-sum of its edges. Every series–parallel graph, or more generally every graph with treewidth at most two, may be formed as a 2-clique-sum of triangles. The same type of result extends to larger values of k: every graph with treewidth at most k may be formed as a clique-sum of graphs with at most k + 1 vertices; this is necessarily a k-clique-sum.

There is also a close connection between clique-sums and graph connectivity: if a graph is not (k + 1)-vertex-connected (so that there exists a set of k vertices the removal of which disconnects the graph) then it may be represented as a k-clique-sum of smaller graphs. For instance, the SPQR tree of a biconnected graph is a representation of the graph as a 2-clique-sum of its triconnected components.

Application in graph structure theory

A strangulated graph, formed as a clique-sum of a maximal planar graph (yellow) and two chordal graphs (red and blue)

Clique-sums are important in graph structure theory, where they are used to characterize certain families of graphs as the graphs formed by clique-sums of simpler graphs. The first result of this type was a theorem of (Wagner 1937), who proved that the graphs that do not have a five-vertex complete graph as a minor are the 3-clique-sums of planar graphs with the eight-vertex Wagner graph; this structure theorem can be used to show that the four color theorem is equivalent to the case k = 5 of the Hadwiger conjecture. The chordal graphs are exactly the graphs that can be formed by clique-sums of cliques without deleting any edges, and the strangulated graphs are the graphs that can be formed by clique-sums of cliques and maximal planar graphs without deleting edges. The graphs in which every induced cycle of length four or greater forms a minimal separator of the graph (its removal partitions the graph into two or more disconnected components, and no subset of the cycle has the same property) are exactly the clique-sums of cliques and maximal planar graphs, again without edge deletions. (Johnson McKee) use the clique-sums of chordal graphs and series–parallel graphs to characterize the partial matrices having positive definite completions.

It is possible to derive a clique-sum decomposition for any graph family closed under graph minor operations: the graphs in every minor-closed family may be formed from clique-sums of graphs that are "nearly embedded" on surfaces of bounded genus, meaning that the embedding is allowed to omit a small number of apexes (vertices that may be connected to an arbitrary subset of the other vertices) and vortices (graphs with low pathwidth that replace faces of the surface embedding). These characterizations have been used as an important tool in the construction of approximation algorithms and subexponential-time exact algorithms for NP-complete optimization problems on minor-closed graph families.

Generalizations

The theory of clique-sums may also be generalized from graphs to matroids. Notably, Seymour's decomposition theorem characterizes the regular matroids (the matroids representable by totally unimodular matrices) as the 3-sums of graphic matroids (the matroids representing spanning trees in a graph), cographic matroids, and a certain 10-element matroid.

References

• "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", Journal of the ACM 52 (6): 866–893, 2005, doi:10.1145/1101821.1101823 .
• "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors", Journal of Computer and System Sciences 69 (2): 166–195, 2004, doi:10.1016/j.jcss.2003.12.001 .
• "Algorithmic graph minor theory: decomposition, approximation, and coloring", Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 637–646, doi:10.1109/SFCS.2005.14, http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf .
• Diestel, Reinhard (1987), "A separation property of planar triangulations", Journal of Graph Theory 11 (1): 43–52, doi:10.1002/jgt.3190110108 .
• Kříž, Igor (1990), "Clique-sums, tree-decompositions and compactness", Discrete Mathematics 81 (2): 177–185, doi:10.1016/0012-365X(90)90150-G .
• Johnson, Charles R.; McKee, Terry A. (1996), "Structural conditions for cycle completable graphs", Discrete Mathematics 159 (1–3): 155–160, doi:10.1016/0012-365X(95)00107-8 .
• "Graph minor theory", Bulletin of the American Mathematical Society 43 (1): 75–86, 2006, doi:10.1090/S0273-0979-05-01088-8 .
• "Graph minors XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B 89 (1): 43–76, 2003, doi:10.1016/S0095-8956(03)00042-X .
• "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B 28 (3): 305–359, 1980, doi:10.1016/0095-8956(80)90075-1 .
• "A generalization of chordal graphs", Journal of Graph Theory 8 (2): 241–251, 1984, doi:10.1002/jgt.3190080206 .
• "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen 114: 570–590, 1937, doi:10.1007/BF01594196 .