TOPICS
Search

k-Tree

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A k-tree, for a positive integer k, is a graph obtained from the complete graph K_(k+1) by repeatedly adding a new graph vertex adjacent to every graph vertex of one k-clique and to no other vertices.

For example, for k=1, the first step adds a new graph vertex with one connecting graph edge to a 1-clique (graph vertex) of the path graph P_2=K_2, giving P_3. Adding another graph vertex with one connecting graph edge 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 a tree with at least two vertices.

k-Trees

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

The case k=2 gives the 2-trees, which are maximal series-parallel graphs. They 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 graph edge would result in a larger treewidth.

Special k-trees are summarized in the following table.

kk-trees
2diamond graph, gem graph, smallest cyclic group graph, triangle graph, 2-triangular grid graph
33-dipyramidal graph, Goldner-Harary graph, tetrahedral graph K_4, triakis tetrahedral graph, tritetrahedral graph

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

npolyhedral 3-trees
4tetrahedral graph K_4
53-dipyramidal graph
6tritetrahedral graph
72-Apollonian network, 3-trees #s 3 and 5
8triakis tetrahedral graph, 7 of the triangulated graphs on 8 nodes
11Goldner-Harary graph

The numbers of k-trees on n=1, 2, ... nodes are summarized in the table below. The table follows the definition above and starts each family at K_(k+1). Some of the cited OEIS sequences also include K_k as a k-tree, giving 1 rather than 0 at n=k.

kOEIScounts
1A0000550, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, ...
2A0545810, 0, 1, 1, 2, 5, 12, 39, 136, 529, 2171, 9368, ...
3A0787920, 0, 0, 1, 1, 2, 5, 15, 58, 275, 1505, 9003, ...
4A0787930, 0, 0, 0, 1, 1, 2, 5, 15, 64, 331, 2150, ...
5A2017020, 0, 0, 0, 0, 1, 1, 2, 5, 15, 64, 342, ...

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

See also

2-Tree, 3-Tree, 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, P45, 2012. https://doi.org/10.37236/2615.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.

Referenced on Wolfram|Alpha

k-Tree

Cite this as:

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

Subject classifications