Treewidth of Cliques
In any tree decomposition of a graph containing a clique there is a node i in T such that contains all the nodes of the clique. This is shown by induction on the size of the clique. The base cases are cliques of size 1 and 2, which follow from the conditions 1 and 2 on a tree decomposition. The inductive case is a graph containing a clique of size k+1, where k is 2 or greater. Let C be the set of nodes in the clique. Since, there are at least three nodes in the clique, call them x, y and z. We know from the induction hypothesis that there are nodes a, b and c in the tree decomposition with
- , .
In a tree there is exactly one path between any two nodes. A second property of trees is that the three paths between a, b and c have a non-empty intersection. Let v be a node in this intersection. From condition 3 on a tree decomposition we get that
This implies that .
It follows from this that the treewidth of a k-clique is k-1.
Read more about this topic: Tree Decomposition
Famous quotes containing the word cliques:
“By the power elite, we refer to those political, economic, and military circles which as an intricate set of overlapping cliques share decisions having at least national consequences. In so far as national events are decided, the power elite are those who decide them.”
—C. Wright Mills (1916–1962)