Graceful Graphs

In 1993, for a Caltech seminar course, we were encouraged to hunt around and find something interesting to research. After some hours digging through math journals in the library, I stumbled across the topic of graceful graphs. Graceful graphs are easy to understand, but have many seemingly simple unresolved questions that no one has been able to answer yet. Chief among these unsolved problems is whether all trees are graceful. I've written a lot more on the topic here.

Graceful graphs lend themselves naturally to computational approaches. I've written several programs to explore this space, but two of the more successful ones are one that enumerates all the graceful graphs up to isomorphism with N edges and one that finds graceful labellings of the double-cones.

I need to dig these out of the archives and post them here, but here's some information about how these programs work.

Enumerating All Graceful Labellings

To enumerate the graceful graphs on N edges, you need to iterate through all possible graceful labellings and then eliminate ones that are isomorphic to labellings already enumerated. The first of these tasks is pretty easy - you just need to count in base N-factorial. The easiest way to do this is to keep a vector of length N, in which member i is between 0 and i inclusive. Start with the all-zero vector, increment the last element until it reaches N-1, then reset it to 0 and increment the next-to-last element (until it reaches N-2, and so on). This approach is illustrated below:

void all_graceful_graphs() {
  int vector[N];
  memset(vector, 0, sizeof(vector));
  do {
    // work with the graceful graph whose edges are
    // (vector[i], vector[i] + N - i)
  }
  while (increment(vector));
}

bool increment(int * vector) {
  int i = N-1;
  while (++vector[i] == i)
  {
    vector[i] == 0;
	if (--i == 0)
	  return false;
  }
  return true;
}

There are many ways to track isomorphism classes of graphs. Nauty provides one of the fastest known implementations of graph isomorphism. For this specialized application, I found that hashing on degree vectors and then (when there is a collision) exhaustively trying all possible mappings between vertices of the same degree works well.

Labelling Particular Graphs

Given a family of graphs to consider, you can also try to find graceful labellings of them. You need to decide whether you want to enumerate all (or many) possible labellings of such graphs, or whether you want to stop at the first labelling.

For example, consider the double cones C_n + K_m^c. These cones take m isolated points (K_m^c) and connect them to all of the n vertices on the cycle C_n. (When m is 1, these are the wheel graphs. When m is 2, these are the double-cones.) I found that for fixed n, it's easy to find labellings that generalize to all values of m.