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