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 0-1 matrix with exactly one 1 in each left-to-right diagonal ( for some ), and the main diagonal () is all zero.

A tree \(T\) is graceful if and only if its adjacency matrix is a graceful matrix. More generally, a graph \(G\) is graceful if and only if the adjacency matrix of the graph \(G \cup K_{E-V+1}^c\) is a graceful matrix.

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 k-th 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 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 , 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.

Example: Equivalence of graceful labeling and graceful adjacency matrix.
(0,5)
(0,4) (1,5)
(0,3) (1,4) (2,5)
(0,2) (1,3) (2,4) (3,5)
(0,1) (1,2) (2,3) (3,4) (4,5)
1
1 0
0 1 0
0 1 0 0
0 0 0 1 0
0 0 0 0 0 0
0.....
00....
000...
0100..
11010.
100000
000011
000110
000000
010010
110100
100000

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 non-zero on some vertex in . Hunter additionally replaced each with a sum of variables, to make this an integer-valued function on the hypercube. See his manuscript for additional ideas.