In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

, analogous to the connected sum

Connected sum

In mathematics, specifically in topology, the operation of connected sum is a geometric modification on manifolds. Its effect is to join two given manifolds together near a chosen point on each...

 operation in topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

. 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

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

 is the 1-clique-sum of its edges. Every series-parallel graph

Series-parallel graph

In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...

, 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

K-vertex-connected graph

In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...

 (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

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 , who proved that the graphs that do not have a five-vertex complete graph as a minor

Minor (graph theory)

In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....

 are the 3-clique-sums of planar graphs with the eight-vertex Wagner graph

Wagner graph

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.-Properties:...

; this structure theorem can be used to show that the four color theorem

Four color theorem

In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...

 is equivalent to the case k = 5 of the Hadwiger conjecture

Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...

. The chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

s are exactly the graphs that can be formed by clique-sums of cliques without deleting any 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 graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s, again without edge deletions. use the clique-sums of chordal graphs and series-parallel graphs to characterize the partial matrices

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 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

Genus (mathematics)

In mathematics, genus has a few different, but closely related, meanings:-Orientable surface:The genus of a connected, orientable surface is an integer representing the maximum number of cuttings along non-intersecting closed simple curves without rendering the resultant manifold disconnected. It...

, 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 algorithm

Approximation algorithm

In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...

s and subexponential-time exact algorithms for NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 optimization problems on minor-closed graph families.

Generalizations

The theory of clique-sums may also be generalized from graphs to matroid

Matroid

In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....

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