Counting graceful labelings of trees: A theoretical and empirical study

详细信息    查看全文

• 作者：David Anick ^{david.anick@rcn.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Database ; Linear regression ; Poisson ; Automorphism group ; Algorithm ; Ubiquitously graceful ; Outlier
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 January 2016
• 年：2016
• 卷：198
• 期：Complete
• 页码：65-81
• 全文大小：1132 K

文摘

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!$n!$ graceful graphs on n+1$n+1$ vertices and select the trees, we prove that b_n$b_n$, the number of all graceful labelings on trees on 18e87047d225cd" title="Click to view the MathML source">n$n$ edges, has growth at least as rapid as $\mathcal{O}\left(\left(n^6\right){\left(\sqrt{24}\right)}^{-n}\left(n!\right)\right)$. Consequently the average number of graceful labelings for a tree on 18e87047d225cd" title="Click to view the MathML source">n$n$ edges also grows superexponentially. We give a heuristic argument why b_n/n!$b_n/n!$ would be expected to be O(n^αβ⁻ⁿ)$O\left(n^{\alpha }{\beta }^{-n}\right)$ with β≈e/2=1.359…$\beta \approx e/2=1.359\dots$. Empirically we show that β≈1.575$\beta \approx 1.575$ based on published values of {b_n}$\left\{b_n\right\}$. By implementing the algorithm we generated a database consisting of the entire set of graceful labelings for all trees T$T$ on 16 or fewer edges, sorted by T$T$. Letting g(T)$g\left(T\right)$ denote the number of graceful labelings of a tree T$T$, for each n≤16$n\le 16$ scatter diagrams reveal a close to linear relationship between ln(g(T))$ln\left(g\left(T\right)\right)$ and ln|Aut(T)|$ln\left|Aut\left(T\right)\right|$, |Aut(T)|$\left|Aut\left(T\right)\right|$ being the size of the automorphism group of T$T$. For 10≤n≤16$10\le n\le 16$, linear regression demonstrates that ln|Aut(T)|$ln\left|Aut\left(T\right)\right|$ and just four other graph invariants account for over 96% of the variance in $\ln \left(g\left(T\right)\right)$. For the 48,629 trees with n=16$n=16$, the root mean square error in predicting ln(g(T))$ln\left(g\left(T\right)\right)$ is 0.236 whereas g(T)$g\left(T\right)$ 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 18e87047d225cd" title="Click to view the MathML source">n$n$, the distribution of vertex degrees associated with each label is very close to Poisson, with the exception of labels 0 and 18e87047d225cd" title="Click to view the MathML source">n$n$. We present two new families of trees that are proved not to be k$k$-ubiquitously graceful. A variety of new questions suggested by the results are given.