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.
- ^ Cluster graphs, Information System on Graph Classes and their Inclusions, accessed 2016-06-26.
- ^ 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.
- ^ 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
© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search