Cluster graph (original) (raw)

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