graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a cluster graph is a graph formed from the

disjoint union In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

s. Equivalently, a graph is a cluster graph

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

it has no three-vertex induced path; for this reason, the cluster graphs are also called -free graphs. They are the

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...

s of the complete multipartite graphsCluster graphs
Information System on Graph Classes and their Inclusions, accessed 2016-06-26. and the 2-leaf powers. The cluster graphs are transitively closed, and every transitively closed undirected graph is a cluster graph. The cluster graphs are the graphs for which adjacency is an

equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. A simpler example is equ ...

, and their connected components are the

equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...

es for this relation.

Related graph classes

Every cluster graph is a block graph, a cograph, and a claw-free graph. Every maximal independent set in a cluster graph chooses a single vertex from each cluster, so the size of such a set always equals the number of clusters; because all maximal independent sets have the same size, cluster graphs are well-covered. The Turán graphs are

s of cluster graphs, with all complete subgraphs of equal or nearly-equal size. The locally clustered graph (graphs in which every

neighborhood A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...

is a cluster graph) are the diamond-free graphs, another family of graphs that contains the cluster graphs. When a cluster graph is formed from cliques that are all the same size, the overall graph is a homogeneous graph, meaning that every

isomorphism In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

between two of its

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

s can be extended to an

automorphism In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...

of the whole graph. With only two exceptions, the cluster graphs and their complements are the only finite homogeneous graphs, and infinite cluster graphs also form one of only a small number of different types of

countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...

homogeneous graphs.

Computational problems

A subcoloring of a graph is a partition of its vertices into induced cluster graphs. Thus, the cluster graphs are exactly the graphs of subchromatic number 1. The computational problem of finding a small set of edges to add or remove from a graph to transform it into a cluster graph is called cluster editing. It is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

but fixed-parameter tractable. Given a complete graph with edge costs (positive and negative) the clique partitioning problem asks for a subgraph that is a cluster graph such that the sum of the costs of the edges of the cluster graph is minimal.. This problem is closely related to the correlation clustering problem.

References

{{reflist Graph families Perfect graphs