Cluster graph

Summary

In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called $P_{3}$-free graphs. They are the complement graphs of the complete multipartite graphs and the 2-leaf powers. The cluster graphs are transitively closed, and every transitively closed undirected graph is a cluster graph.