K-tree

The Goldner–Harary graph, an example of a planar 3-tree.

In graph theory, a k-tree is a chordal graph 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.

The k-trees are exactly the maximal graphs with a given treewidth, graphs to which no more edges can be added without increasing their treewidth. The graphs that have treewidth at most k are exactly the subgraphs of k-trees, and for this reason they are called partial k-trees.

Every k-tree may be formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex has exactly k neighbors that form a clique.

Certain k-trees with k ≥ 3 are also the graphs formed by the edges and vertices of stacked polytopes, polytopes formed by starting from a simplex and then repeatedly gluing simplices onto the faces of the polytope; this gluing process mimics the construction of k-trees by adding vertices to a clique. Every stacked polytope forms a k-tree in this way, but not every k-tree comes from a stacked polytope: a k-tree is the graph of a stacked polytope if and only if no three (k + 1)-vertex cliques have k vertices in common.

1-trees are the same as unrooted trees. 2-trees are maximal series-parallel graphs, and include also the maximal outerplanar graphs. Planar 3-trees are also known as Apollonian networks. In higher-dimensional geometry, the stacked polytopes have graphs that are k-trees.