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

, a branch of mathematics, a cluster graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

formed from the

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

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

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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bi ...

it has no three-vertex

induced path 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 ...

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

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.

Related graph classes

Every cluster graph is a

block graph In graph theory, a branch of combinatorial mathematics, a block graph or clique tree. is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after ...

, a

cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...

, and a

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

. 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 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 In mathematics, a ''k''-ultrahomogeneous graph is a graph in which every isomorphism between two of its induced subgraphs of at most ''k'' vertices can be extended to an automorphism of the whole graph. A ''k''-homogeneous graph obeys a weakened v ...

, meaning that every

isomorphism In mathematics, an isomorphism is a structure-preserving mapping 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 them. The word i ...

between two of its

induced subgraph In the mathematical field of 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. Definit ...

s can be extended to an 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 numbers ...

homogeneous graphs.

Computational problems

A subcoloring of a graph is a partition of its vertices into

induced Induce may refer to: * Induced consumption * Induced innovation * Induced character * Induced coma * Induced menopause * Induced metric * Induced path * Induced topology * Induce (musician), American musician See also * Inducement (disambiguation ...

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 may refer to: Science and technology Astronomy * Cluster (spacecraft), constellation of four European Space Agency spacecraft * Asteroid cluster, a small asteroid family * Cluster II (spacecraft), a European Space Agency mission to study t ...

. It is

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

but

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...

References

{{reflist Graph families Perfect graphs