Efficient Enumeration of Graceful Permutations

Abstract

A graceful $n$-permutation is a graceful labeling of an $n$-vertex path $P_n$. In this paper, we improve the asymptotic lower bound on the number of such permutations from $\mathrm{\Omega }\left({\left(\frac{5}{3}\right)}^n\right)$ to $\mathrm{\Omega }\left({2.37}^n\right)$. This is a computer-assisted proof based on an effective algorithm that enumerates graceful $n$-permutations. Our algorithm is also presented in detail.