Cluster graph

This article is about disjoint unions of complete graphs. For graphs with clustered vertices, see clustered planarity. For visualizations of clusterings, see cluster diagram.
A cluster graph with clusters (complete subgraphs) of sizes 1, 2, 3, 4, 4, 5, and 6

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[1] and the 2-leaf powers.[2] The cluster graphs are transitively closed, and every transitively closed undirected graph is a 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. ^ Cluster graphs, Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
  2. ^ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, doi:10.1006/jagm.2001.1195.
  3. ^ McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics, 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101