TOPICS

# k-Tree

The -tree on vertices is the complete graph . -trees on vertices are then obtained by joining a new vertex to -cliques the -trees on vertices in all possible ways.

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

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 -trees correspond to the maximal graphs with treewidth , where "maximal" means that the addition of any edge would result in a larger treewidth.

Special -trees are summarized in the following table.

 -trees 2 diamond graph, gem graph, smallest cyclic group graph, triangle graph, 2-triangular grid graph 3 3-dipyramid graph, Goldner-Harary graph, tetrahedral graph, triakis tetrahedral graph, tritetrahedral graph

Some Polyhedral 3-trees on nodes are summarized below.

 polyhedral 3-trees 4 tetrahedral graph 5 3-dipyramid graph 6 tritetrahedral graph 7 2-Apollonian network, 3-trees #s 3 and 5 8 triakis tetrahedral graph, 7 of the triangulated graphs on 8 nodes 11 Goldner-Harary graph

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

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

-trees are -uniquely colorable (Xu 1990).

Cone Graph, Tree, Treewidth

## Explore with Wolfram|Alpha

More things to try:

## References

Gainer-Dewar, A. "-Species and the Enumeration of -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 -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