Labeling

Certain trees took much longer to label than other trees. While we do not have a formal description of how to determine which trees take more time than others, the labeling itself which is produced by $\mathit{Label}(G)$ carries some indication of how long it took to label.

Because the the vertices are labeled in order, and attempts are made to assign vertex labels in order, we can make basic inferences. For instance, if $\mathit{Label}(G)$ returns (0 3 1 2) for some given $G$, we know that the assignment $\mathit{Label}(0) \leftarrow 0$ took place as the first assignment, and was never retracted. Vertex 1 must have been adjacent (as 0 and 3 must be adjacent in a 4 vertex graceful labeling), so the assigment $\mathit{Label}(1) \leftarrow 3$ was made immediately, and never retracted. These basic inferences give us some idea as to how much backtracking was performed during labeling.

As an example, there are 106 unique trees on 10 vertices. Of the labelings that our algorithm found for these trees, 82 begin $(0,9,1,8,...)$. 96 begin with $(0,9,1..)$. In fact, only 4 did not begin with zero. One machine used for development, labeling all 106 trees took 2m50s. These 4 graphs whose labels did not begin with 0 required 37s to label. The other 102 graphs then took, on average, only 1.3s to label. Certainly a few tree take much longer to label than others.