K-Tree

[math]\displaystyle{ k }[/math]-Tree --- [math]\displaystyle{ k }[/math]-дерево.

1. [math]\displaystyle{ k }[/math]Tree is a graph which can be recursively defined as follows. A clique with [math]\displaystyle{ k+1 }[/math] vertices is a [math]\displaystyle{ k }[/math]-tree, and a [math]\displaystyle{ k }[/math]-tree with [math]\displaystyle{ n+1 }[/math] vertices can be obtained from [math]\displaystyle{ k }[/math]-tree with [math]\displaystyle{ n }[/math] vertices by making a new vertex adjacent to exactly all vertices of a [math]\displaystyle{ k }[/math]-clique. Subgraphs of [math]\displaystyle{ k }[/math]-trees are called partial [math]\displaystyle{ k }[/math]-trees. If a partial [math]\displaystyle{ k }[/math]-tree [math]\displaystyle{ G }[/math] is a subgraph of a [math]\displaystyle{ k }[/math]-tree [math]\displaystyle{ H }[/math], we call [math]\displaystyle{ H }[/math] a [math]\displaystyle{ k }[/math]-tree embedding for [math]\displaystyle{ G }[/math].

The minimum value [math]\displaystyle{ k }[/math] for which a graph is a subgraph of a [math]\displaystyle{ k }[/math]-tree is called a treewidth of a graph. It is not difficult to see that [math]\displaystyle{ k }[/math]-trees are partial [math]\displaystyle{ l }[/math]-trees for every [math]\displaystyle{ l \geq k }[/math]. Hence, every graph of treewidth [math]\displaystyle{ k }[/math] is a partial [math]\displaystyle{ l }[/math]-tree for every [math]\displaystyle{ l \geq k }[/math], i.e., the class of partial [math]\displaystyle{ k }[/math]-trees is exactly the class of graphs of treewidth at most [math]\displaystyle{ k }[/math].

It is clear that every graph [math]\displaystyle{ G = (V,E) }[/math] with [math]\displaystyle{ |V| = n }[/math] is a partial [math]\displaystyle{ n }[/math]-tree. The problem to determine the smallest [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ G }[/math] is a partial [math]\displaystyle{ k }[/math]-tree, however, is NP-complete.

2. [math]\displaystyle{ k }[/math]Tree is a spanning tree in which every vertex has degree at most [math]\displaystyle{ k }[/math].