Counting graceful labelings of trees: A theoretical and empirical study

摘要

The conjecture that every tree has a graceful labeling has inspired a lot of good mathematics since it was first articulated in 1967. By analyzing an algorithm whose essence is to run through all n! graceful graphs on n + 1 vertices and select the trees, we prove that b(n), the number of all graceful labelings on trees on n edges, has growth at least as rapid as O((n(6)) (root 24)(-n)(n!)). Consequently the average number of graceful labelings for a tree on n edges also grows superexponentially. We give a heuristic argument why b(n)! would be expected to be O(n(alpha)beta(-n)) with beta approximate to e/2 = 1.359.... Empirically we show that beta approximate to 1.575 based on published values of {b(n)}. By implementing the algorithm we generated a database consisting of the entire set of graceful labelings for all trees Ton 16 or fewer edges, sorted by T. Letting g(T) denote the number of graceful labelings of a tree T, for each n <= 16 scatter diagrams reveal a close to linear relationship between In(g(T)) and In vertical bar Aut(T)vertical bar, vertical bar Aut(T)vertical bar being the size of the automorphism group of T. For 10 <= n <= 16, linear regression demonstrates that ln vertical bar Aut(T)vertical bar and just four other graph invariants account for over 96% of the variance in ln(g(T)). For the 48,629 trees with n = 16, the root mean square error in predicting In(g(T)) is 0.236 whereas g(T) ranges over seven orders of magnitude. A simple criterion is developed to predict which trees have an exceptionally large number of graceful labelings. Trees whose number of graceful labelings is exceptionally small fall into two already known families of caterpillar graphs. Over the full set of graceful labelings for a given n, the distribution of vertex degrees associated with each label is very close to Poisson, with the exception of labels 0 and n. We present two new families of trees that are proved not to be k-ubiquitously graceful. A variety of new questions suggested by the results are given. (C) 2015 Elsevier B.V. All rights reserved.