Trees

Scenario 1

If G is a tree, then av(G) ≤ T₁(G) ≤ av (G) + 1, where av (G) is the valency sequence, and these bounds are tight.

Scenario 2

If we orient each edge of a tree T to point toward its lesser subtree (and orient the size-center edge, if there is one, arbitrarily), then we say T has a lesser subtree orientation, or LSO.

Any vertex in a tree T with an LSO has at most one incoming edge.

A tree with an LSO has a unique source vertex, which we will call the size-center vertex.

The lesser subtree sequence, s(v), of a vertex v in a tree with an LSO is the non-decreasing sequence of the sizes of the lesser subtrees on its outgoing edges. Thus, s(v) is empty if and only if v is a leaf, has length deg (v) if and only if v is the size-center vertex, and has length deg(v) − 1 otherwise.

Let Q(T) be the number of different sizes of the lesser subtrees of a tree T, and let R(T) be the number of distinct lesser subtree sequences in the LSO of T.

Algorithm:

Input: The target graph, an unrooted tree T.

Output: A set of R(T) tile types using Q(T) bond-edge types from which T may be constructed, but nothing smaller.

1. Create a lesser subtree orientation for T. Take the size-center vertex to be the root. (Note that all edges will be then be directed downward in the tree.)

2. For each directed edge (u, v) label the edge with bond-edge type b_k where k is the size of the subtree rooted at v.

3. The tile types are given by the labeled orientation of the graph.

The minimum number of bond edges required is equal to the number of different sizes of the lesser subtrees (i.e. B₂ (T) = Q(T)).

The minimum number of tile types required corresponds to the number of distinct lesser subtree sequences (i.e. T₂ (T) = R(T))

Scenario 3

Here we assume the height is the number of vertices, not edges, so a single vertex has height 1, and the tree with two vertices joined by an edge has height 2. Let I(T) denote the number of induced subtree isomorphisms within the tree.

Algorithm

Input: The target graph, a tree T.

Output: A set of I(T) tiles using I (T) − 1 bond-edge types from which T may be constructed but no smaller or same size graphs.

1. Create a lesser subtree orientation of the graph, and choose the unique size center vertex to be the root. (Note that all edges will be directed downward in the tree.)

2. Label all edges to leaf nodes b₀.

3. Set j=1.

4. for i from h to 1, let i = i − 1, and examine each edge (u, v) from a node at level i − 1 to a node at level i successively.

- If the edge is already labeled b₀ continue.

- Examine the subtree rooted at v.

- If it is isomorphic to the subtree below edge e for any edge e that has already been labeled, then give (u, v) the same label as edge e, otherwise, let j = j + 1, and label (u, v) by b_j .

5. The tile types are given by the labeled orientation of the graph.

Running Time: The running time of this algorithm is O(n³) since each tree isomorphism may be checked in linear time [AHU94].

The number of bond edges needed will equal the number of induced subgraph isomorphms minus one (i.e. B₃ (T) = I (T) − 1).

The number of tile types needed will equal the number of induced subgraph isomorphms (i.e. T₃ (T) = I (T)).