graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

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

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

, analogous to the

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. This construction plays a key role in the classifi ...

operation in

topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...

. 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 In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A ( ...

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. 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 graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...

s or

strangulated graph In graph theoretic mathematics, a strangulated graph is a graph in which deleting the edges of any induced cycle of length greater than three would disconnect the remaining graph. That is, they are the graphs in which every peripheral cycle i ...

s, no edges should be removed. In other contexts, such as the

SPQR-tree In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...

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 In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seven ...

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 In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

: If two graphs have treewidth at most ''k'', so does their ''k''-clique-sum. Every

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

is the 1-clique-sum of its edges. Every

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

, or more generally every graph with

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

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 In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgr ...

: 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 In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...

of a biconnected graph is a representation of the graph as a 2-clique-sum of its

triconnected component In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...

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 are the 3-clique-sums of planar graphs with the eight-vertex

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 As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, ...

; this structure theorem can be used to show that the four color theorem is equivalent to the case ''k'' = 5 of the

Hadwiger conjecture There are several conjectures known as the Hadwiger conjecture or Hadwiger's conjecture. They include: * Hadwiger conjecture (graph theory), a relationship between the number of colors needed by a given graph and the size of its largest clique mino ...

. The

s are exactly the graphs that can be formed by clique-sums of cliques without deleting any edges, and the

s are the graphs that can be formed by clique-sums of cliques and

maximal 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. In other words, it can be drawn in such a way that no edges cros ...

s without deleting edges. The graphs in which every

induced cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

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. use the clique-sums of chordal graphs and series–parallel graphs to characterize the partial

matrices Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

having

positive definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular: * Positive-definite bilinear form * Positive-definite f ...

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 ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...

, 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 In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition ...

that replace faces of the surface embedding). These characterizations have been used as an important tool in the construction of

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

s and subexponential-time exact algorithms for

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

optimization problems on minor-closed graph families.

Generalizations

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

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

s. Notably, ''Seymour's decomposition theorem'' characterizes the

regular matroid In mathematics, a regular matroid is a matroid that can be represented over all fields. Definition A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". On ...

s (the matroids representable by totally unimodular matrices) as the 3-sums of

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called ...

s (the matroids representing spanning trees in a graph), cographic matroids, and a certain 10-element matroid..

Notes

References

*. *. *. *. *. *. *. *. *. *. *. {{DEFAULTSORT:Clique-Sum Graph operations Graph minor theory