Clique-sum

File:Clique-sum.svg

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

In graph theory, a branch of mathematics, a 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 possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have at most k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum 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

File:Strangulated graph.svg

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 (1996) 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

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .