Cluster graph

[3] The cluster graphs are the graphs for which adjacency is an equivalence relation, and their connected components are the equivalence classes for this relation.

[1] 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.

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

[6] 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.

[8] 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.