Ingraph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique.[1][2]
The k-trees are exactly the maximal graphs with a treewidthofk ("maximal" means that no more edges can be added without increasing their treewidth).[2] They are also exactly the chordal graphs all of whose maximal cliques are the same size k + 1 and all of whose minimal clique separators are also all the same size k.[1]
1-trees are the same as trees. 2-trees are maximal series–parallel graphs,[3] and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks.[4]
The graphs that have treewidth at most k are exactly the subgraphsofk-trees, and for this reason they are called partial k-trees.[2]
The graphs formed by the edges and vertices of k-dimensional stacked polytopes, polytopes formed by starting from a simplex and then repeatedly gluing simplices onto the faces of the polytope, are k-trees when k ≥ 3.[5] This gluing process mimics the construction of k-trees by adding vertices to a clique.[6]Ak-tree is the graph of a stacked polytope if and only if no three (k + 1)-vertex cliques have k vertices in common.[7]
