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).