[Information Index] [Generation Index] [COS homepage]

Information on Free Trees

A free tree is an undirected graph that is both connected and acyclic.

A center of a free tree is a node which minimizes the maximal distance to all other nodes in the tree. We represent a free tree as a rooted tree by picking a center of the free tree to be the root. For trees, there might be either one or two centers. If it has one center, we say that it is unicentered. If it has two centers, we say that it is bicentered. For a bicentered free tree, we pick as the root the center which yields the lexicographically largest level sequence for the tree (see the Information on Rooted Trees for a description of the level sequence of a tree). Each unlabeled free tree can be uniquely represented by a canonic rooted tree.

The figure on the left shows a free tree with two centers, a and b. If we root the tree at a, we get the level sequence 0 1 2 2 1 1 1. If we root the tree at b, we get the level sequence 0 1 2 2 2 1 1. Since rooting the tree at b yields a lexicographically larger level sequence, we choose b as the root. The figure on the right shows a free tree with only one center a. The level sequence of the free tree on the left is 0 1 2 2 2 1 1, that of the one on the right is 0 1 2 2 1 2 1.

The diameter of a tree is the length of the longest path in the tree. The tree on the left has diameter 3, the one on the right has diameter 4. Our program will generate unlabeled free trees of n nodes with maximum degree m, and diameter between lb and ub.

For n = 1,2,3,...,15 the number of free trees is 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741. This is sequence A000055(M0791) in Neil J. Sloane's database of integer sequences.

A Cayley 3-free tree is a free tree with max degree 3. For n = 1,2,3...15, the number of Cayley 3-free trees is 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132. This is sequence A000672(M0326) in Neil J. Sloane's database of integer sequences.

A Cayley 4-free tree (sometimes called an unrooted quartic tree) is a free tree where each vertex has degree 4 or less. For n = 1,2,3...15, the number of Cayley 4-free trees is 1,1,1,2,3,5,9,18,35,75,159,355,802,1858,4347. This is sequence A000602(M0718) in Neil J. Sloane's database of integer sequences.

The asymptotic number of free trees has been studied by Otter and others. You may click here for further information.

The algorithm used here is from the paper The advantages of forward thinking in generating trees, Gang Li and Frank Ruskey, manuscript, 1995. An outline was presented at SODA; see the downloadable paper for further details.


Programs available:

Further Links:


[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last modified on Tuesday, 24-May-2011 10:52:28 PDT.
[Error Opening Counter File -- Click for more info]
©Frank Ruskey, 1995-2003.