On the Enumeration of a Class of Non-Graceful Graphs (?)

A simple graph G is a graceful graph if there exists a graceful labeling of the vertices of G. If we cannot gracefully label the vertices of G, then G is a non-graceful graph. A result by Rosa provides a sucient condition for a graph to be non-graceful: “If a graph G is simple, even, and has e edges, with e 1 or 2 (mod 4), then G is not graceful.” This condition implies an infinite subclass of non-graceful graphs, which we define to be R .B y the degree-sum formula for graphs, the sum of the degrees of a graph G is equal to 2e. We systematically enumerate graphs in R by first generating all even partitions of 2e (where e 1 or 2 (mod 4)) using Maple. We then use the Havel-Hakimi procedure to determine which of these generated “number sequences” are graphic sequences. These graphic sequences determine all of the simple, even, graphs in R (both connected and disconnected) with e 1 or 2 (mod 4) edges.