I read two definitions of cluster graphs that seem in conflict to me. One is from Koller:

We begin by defining a cluster graph — a data structure that provides a graphical flowchart of the factor-manipulation process. Each node in the cluster graph is a cluster, which is associated with a subset of variables; the graph contains undirected edges that connect clusters whose scopes have some non-empty intersection. We note that this definition is more general than the data structures we use in this chapter, but this generality will be important in the next chapter, where we significantly extend the algorithms of this chapter.

Definition 10.1: A cluster graph $\mathcal{U}$ for a set of factors $\Phi$ over $\mathcal{X}$ is an undirected graph, each of whose nodes $i$ is associated with a subset $\boldsymbol{C}_i \subseteq \mathcal{X}$ . A cluster graph must be family-preserving — each factor $\phi \in \Phi$ must be associated with a cluster $\boldsymbol{C}_i$, denoted $\alpha(\phi)$, such that $\text{Scope}[\phi] \subseteq \boldsymbol{C}_i$. Each edge between a pair of clusters $\boldsymbol{C}_i$ and $\boldsymbol{C}_j$ is associated with a sepset $\boldsymbol{S}_{i,j} \subseteq \boldsymbol{C}_i \cap \boldsymbol{C}_j$.

Then I saw another definition on Wikipedia

Source: page 346, Koller, Daphne, and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.

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.

Source: https://en.wikipedia.org/wiki/Cluster_graph#:~:text=In%20graph%20theory%2C%20a%20branch,called%20P3%2Dfree%20graphs.

Unless I am reading this wrong, Koller's definition makes no requirement for completeness. According to Koller's definition, it seems to me that each $\boldsymbol{C}_{i}$ need only be a subset of $\mathcal{X}$ with an arbitrary configuration of edges within the cluster, no specification that it need be a complete graph.

If I am correct these definitions are incompatible, can someone explain which one is correct?

If I am incorrect, I'd love to know why.


1 Answer 1


You are reading it correctly. Those are two different uses of the word "cluster graph".

In graph theory, and usually in computer science, when you refer to a cluster graph it is of the latter kind.

For graph classes, the holy scripture is graphclasses.org, in which you can find Graphclass: cluster

Graphclass: cluster


A graph is a cluster graph if it is a disjoint union of cliques.

Equivalent classes:

  • 2-leaf power
  • $P_3$-free

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.