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, , on edges and vertices, and extend it with additional isolated vertices so that it has vertices (that is, ). The adjacency matrix is a graceful matrix if there exists a permutation matrix such that is a 01 matrix with exactly one 1 in each lefttoright diagonal ( for some ), and the main diagonal () is all zero.
Proof Sketch: Construct a pyramid with rows. In the top row (row ), there is a single entry . In row there are two entries, and . In the kth row, there are entries, all the such that . 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 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 , 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” satisfy .
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 , arbitrarily assign directions to all the edges and then define a polynomial . Define . T has a graceful labelling if and only if is nonzero on some vertex in . Hunter additionally replaced each with a sum of variables, to make this an integervalued function on the hypercube. See his manuscript for additional ideas.