Special Labeling

Special trees generated by Algorithm 1 have the property that the vertex $z$, to which all paths have one endpoint adjacent, is always vertex 0 in the adjacent matrix. Furthermore, the endpoint of the first path adjacent to $z$ is 1, the endpoint of the second is $(t+1)+1$, the third $(t+1)+(t+1)+1$, and so on. In fact, the vertices of the tree are placed in the adjacency matrix as shown in Figure 2.

Figure 2: Structure of the vertices in a special tree

It may not immediately be clear from the labeling, but the order in which the labels are assigned begins with 0 at the `root', and the rest proceed in the order shown in Figure 3.

Figure: Applying the labels to $\mathit{Special}(3,2)$

Knowing that vertices in the special tree will be placed in the adjacency matrix in this way allows us to define a simple procedure to assign each vertex a label in such that a way that the special tree has a graceful labeling after all assignments have been made. This labeling algorithm is efficient in that the labeling it produces is graceful, and no `backtracking' or trial and error is necessary. We call this procedure $\mathit{SpecialLabel}(k,t)$ which will assign the labels of vertices $0,1,...,k(t+1)$ such that a tree with such vertices created by $\mathit{Special}(k,t)$ is gracefully labeled.

In this algorithm, for simplification of indexing, we actually assign the labels to a matrix representing the vertices in the `grid' that appears in the graphical representation of the tree. For instance, in Figure 3, the label matrix would end as

$$\mathit{labels} = \left[ \begin{array}{ccc} 9 & 6 & 3 \\ 1 & 4 & 7 \\ 8 & 5 & 2 \end{array}\right]$$