TOPICS
Search

k-Tree


The k-tree on k+1 vertices is the complete graph K_(k+1). k-trees on n>k+1 vertices are then obtained by joining a new vertex to k-cliques the k-trees on n-1 vertices in all possible ways.

For example, for k=1, the first step adds a new vertex with connecting edge to the 1-cliques (vertices) of the path graph P_2=K_2, giving P_3. Adding another vertex with connecting edges to P_3 gives the claw graph K_(1,3) and P_4. Similarly, a third iteration gives the star graph S_5, fork graph, and P_5. As can be seen by this construction process, a 1-tree is simply a normal tree.

k-Trees

The first few 2- and 3-trees are illustrated above.

2-trees are maximal series-parallel graphs, which include the maximal outerplanar and Dorogovtsev-Goltsev-Mendes graphs.

The k-trees correspond to the maximal graphs with treewidth k, where "maximal" means that the addition of any edge would result in a larger treewidth.

Special k-trees are summarized in the following table.

Some Polyhedral 3-trees on n nodes are summarized below.

The numbers of k-trees on n=1, 2, ... nodes are summarized in the table below.

kOEIScounts
1A000055 0, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, ...
2A054581 0, 0, 1, 1, 2, 5, 12, 39, 136, 529, 2171, 9368, ...
3A078792 0, 0, 0, 1, 1, 2, 5, 15, 58, 275, 1505, 9003, ...
4A078793 0, 0, 0, 0, 1, 1, 2, 5, 15, 64, 331, 2150, ...
5A201702 0, 0, 0, 0, 0, 1, 1, 2, 5, 15, 64, 342, ...

k-trees are (k+1)-uniquely colorable (Xu 1990).


See also

Cone Graph, Tree, Treewidth

Explore with Wolfram|Alpha

References

Gainer-Dewar, A. "Gamma-Species and the Enumeration of k-Trees." Elec. J. Combin. 19, No. 4, Article P45, 2012.Harary, F. and Palmer, E. M. "On Acyclic Simplicial Complexes." Mathematika 15, 115-122, 1968.Patil, H. P. "On the Structure of k-Trees." J. Combin., Information and System Sci. 11, 57-64, 1986.Sloane, N. J. A. Sequences A000055, A054581, A078792, A078793, and A201702 in "The On-Line Encyclopedia of Integer Sequences."Xu, S. J. "The Size of Uniquely Colorable Graphs." J. Combin. Th. 50, 319-320, 1990.

Cite this as:

Weisstein, Eric W. "k-Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/k-Tree.html

Subject classifications