@*Intro. Here's an easy way to calculate the number of graceful labelings that have $m$ edges and $n$ nonisolated vertices, for $0\le n\le m+1$, given~$m>1$. I subdivide into connected and nonconnected graphs. The idea is to run through all $m$-tuples $(x_1,\ldots,x_m)$ with $0\le x_j\le m-j$; edge $j$ will go from the vertex labeled $x_j$ to the vertex labeled $x_j+j$. I consider only the labelings in which $x_{m-1}=1$; in other words, I assume that edge $m-1$ runs from 1~to~$m$. (These are in one-to-one correspondence with the labelings for which that edge runs from 0~to~$m{-}1$.) But I multiply all the answers by~2; hence the total over all $n$ is exactly~$m!$. I could go through those $m$-tuples in some sort of Gray code order, with only one $x_j$ changing at a time. But I'm not trying to be tricky or extremely efficient. So I simply use reverse colexicographic order. That is, for each choice of $(x_{j+1},\ldots,x_m)$, I run through the possibilities for~$x_j$ from $m-j$ to~0, in decreasing order. @d maxm 20 /* this is plenty big, because $20!$ is a 61-bit number */ @ I do, however, want to have some fun with data structures. Every vertex is represented by its label. Vertex~$v$, for $0\le v\le m$, is isolated if and only if label~$v$ has not been used in any of the edges. (In particular, vertices 0, 1, and~$m$ are never isolated, because of the assumption above.) It's easy to maintain, for each vertex, a linked list of all its neighbors. These lists are stacks, since they change in first-in-last-out fashion. It's also easy to maintain a dynamic union-find structure, because of the first-in-last-out behavior of this algorithm. @ OK, let's get going. @c #include #include int mm; /* command-line parameter */ @; main(int argc,char*argv[]) { register j,k,l,m; @; @; while (1) { @; @; } done:@+@; } @ @= if (argc!=2 || sscanf(argv[1],"%d", &mm)!=1) { fprintf(stderr,"Usage: %s m\n", argv[0]); exit(-1); } m=mm; if (m<2 || m>maxm) { fprintf(stderr,"Sorry, m must be between 2 and %d!\n", maxm); exit(-2); } @ @= for (j=1;x[j]==0;j++) { @; } if (j==m-1) goto done; @; x[j]--; @; for (j--;j;j--) { x[j]=m-j; @; } @*Graceful structures. An unusual --- indeed, somewhat amazing --- data structure works well with graceful graphs. Suppose $v$ has neighbors $w_1$, \dots, $w_t$. Let $f_v(w)=w-v$, if $w>v$; $f_v(w)=m+v-w$, if $w= @; for (j=m;j;j--) { x[j]=m-j; @; } @ @= { register int p,u,v,uu,vv; u=x[j]; v=u+j; @; p=arcs[u]; if (!p) active++; link[j]=p, arcs[u]=j; p=arcs[v]; if (!p) active++; link[m+j]=p, arcs[v]=m+j; } @ @= { register int p,u,v,uu,vv; u=x[j]; v=u+j; p=link[m+j]; /* at this point |arcs[v]=m+j| */ arcs[v]=p; if (!p) active--; p=link[j]; /* at this point |arcs[u]=j| */ arcs[u]=p; if (!p) active--; @; } @ Two vertices are equivalent if they belong to the same component. We use a classic union-find data structure to keep of equivalences: The invariant relations state that |parent[v]<0| and |size[v]=c| if |v| is the root of an equivalence class of size~|c|; otherwise |parent[v]| points to an equivalent vertex that is nearer the root. These trees have at most$\lg m$levels, because we never merge a tree of size~|c| into a tree of size |= for (j=0;j<=m;j++) parent[j]=-1,size[j]=1; /* and |l=0| */ l=0; @ @= for (uu=u;parent[uu]>=0;uu=parent[uu]) ; for (vv=v;parent[vv]>=0;vv=parent[vv]) ; if (uu==vv) move[l]=-1; else if (size[uu]<=size[vv]) parent[uu]=vv, move[l]=uu, size[vv]+=size[uu]; else parent[vv]=uu, move[l]=vv, size[uu]+=size[vv]; l++; @ Dynamic union-find is ridiculously easy because, as observed above, the operations are strictly last-in-first-out. And we didn't clobber the |size| information when merging two classes. @ @= l--; uu=move[l]; if (uu>=0) { vv=parent[uu]; /* we have |parent[vv]<0| */ size[vv]-=size[uu]; parent[uu]=-1; } @ @= int active; /* this many vertices are currently labeled (not isolated) */ int parent[maxm+1], size[maxm+1], move[maxm]; /* the union-find structures */ int arcs[maxm+1]; /* the first neighbor of |v| */ int link[2*maxm+1]; /* the next element in a list of neighbors */ int x[maxm+1]; /* the governing sequence of edge choices */ @*Doing it. Now we're ready to harvest the routines we've built up. [A puzzle for the reader: Is |parent[m]| always negative at this point? Answer: Not if, say,$m=7$and$(x_1,\ldots,x_m)=(5,4,3,2,0,1,0)\$.] @= for (k=parent[m];parent[k]>=0;k=parent[k]) ; if (size[k]==active) connected[active]++; else disconnected[active]++; @ @= printf("Counts for %d edges:\n", m); for (k=2;k<=m+1;k++) if (connected[k]+disconnected[k]) { printf("on %5d vertices, %lld are connected, %lld not\n", k,2*connected[k],2*disconnected[k]); totconnected+=2*connected[k],totdisconnected+=2*disconnected[k]; } printf("Altogether %lld connected and %lld not.\n", totconnected,totdisconnected); @ @= unsigned long long connected[maxm+2],disconnected[maxm+2]; unsigned long long totconnected,totdisconnected; @*Index.