Alternate formulations of graceful graphs may provide insights or lead to solutions of open problems. Here are some I had in my notes.

Graceful Matrix

Consider a graceful graph, \(G\), on \(E\) edges and \(V\) vertices, and extend it with additional isolated vertices so that it has \(E+1\) vertices (that is, \(G \cup K_{E-V+1}^c\)). The adjacency matrix \(A={a_ij}\) is a graceful matrix if there exists a permutation matrix \(P\) such that \(PAP^T\) is a 0-1 matrix with exactly one 1 in each left-to-right diagonal (\(j-i=k\) for some \(k > 0\)), and the main diagonal (\(j=i\)) is all zero.

Proof Sketch: Construct a pyramid with \(E\) rows. In the top row (row \(E\)), there is a single entry \((0,E)\). In row \(E-1\) there are two entries, \((0,E-1)\) and \((1,E)\). In the k-th row, there are \(E-k+1\) entries, all the \((u,v)\) such that \(v - u = k\). Mark the cases corresponding to edges in the graph with 1, and all the others with 0. Extend the pyramid with another row of all zeros. Rotate the pyramid so that the entry \((0,E)\) is in the lower left corner and the bottom all-zero row is now the main diagonal, and use symmetry to complete this across the diagonal into a square matrix, which is seen to be the adjacency matrix of the graph \(G \cup K_{E-V+1}^c\), and has the stated property of exactly one 1 in each diagonal except the main diagonal which is all-zero. Thus, the adjacency matrix is a graceful matrix.

In “Semibandwidth of Bipartite Graphs and Matrices” (Brualdi & McDougal, 1990), a graceful matrix is one for which the “triangular numbers” \(t'_k\) satisfy \(t'_k - t'_{k-1} = 1\).

Polynomials

Hunter S. Snevily developed a method of representing graceful labelings as polynomials in a 1997 manuscript titled “A polynomial approach to the graceful tree conjecture,” which was cited in his 2000 paper with André Kézdy, “Distinct Sums Modulo n and Tree Embeddings.” I didn’t see this paper online anywhere, and because he died in 2013, it’s perhaps lost. However, I have an earlier draft that Hunter gave me.

His idea was this: Given a tree T with vertices \(x_0, x_1, ..., x_n\), arbitrarily assign directions to all the edges \(e_i = (x_{i_1},x_{i_2})\) and then define a polynomial \(p_T(\mathbf{x}) = p_T(x_0, x_1, ..., x_n) = \prod_{n \ge i > j \ge 1} (((x_{i_2} - x_{i_1}) - (x_{j_2} - x_{j_1})) \cdot ((x_{i_2} - x_{i_1}) - (x_{j_1} - x_{j_2})))\). Define \(f'_T(\mathbf{x}) = \prod_{n \ge i > j \ge 0}(x_i - x_j) \cdot p_T(\mathbf{x})\). T has a graceful labelling if and only if \(f'_T\) is non-zero on some vertex \(\mathbf{x}\) in \([0,n]^{n+1}\). Hunter additionally replaced each \(x_i\) with a sum of \(n\) variables, to make this an integer-valued function on the \(\{0,1\}^{n^2+n}\) hypercube. See his manuscript for additional ideas.