Graceful Graphs / Ideas Related to Graceful Graphs
Updated: 23 May 2014
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_{EV+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 01 matrix with exactly one 1 in each lefttoright diagonal (\(ji=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 \(E1\) there are two entries, \((0,E1)\) and \((1,E)\). In the kth row, there are \(Ek+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 allzero 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_{EV+1}^c\), and has the stated property of exactly one 1 in each diagonal except the main diagonal which is allzero. 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'_{k1} = 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 nonzero 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 integervalued function on the \(\{0,1\}^{n^2+n}\) hypercube. See his manuscript for additional ideas.