\datethis @*Intro. This program finds all of the nonisomorphic graceful labelings of the graph $K_{m,n}$. I based it on {\mc BACK-GRACEFUL-KMP2}, which handles a more difficult problem. The graph $K_{m,n}$ is hardwired'' into the logic of this program. It has $q=mn$ edges. Although I won't be able to let $m$ and $n$ get extremely large, I'm hoping to see a pattern from which some conjectures will follow. (Even some theorems, if I'm lucky.) Please excuse me for writing this in a rush. A lot of the code has inherited awkwardness from its history. @d o mems++ /* count one mem */ @d oo mems+=2 /* count two mems */ @d ooo mems+=3 /* count three mems */ @d delta 10000000000; /* report progress every |delta| or so mems */ @d O "%" /* used for percent signs in format strings */ @d maxmn 16 /* |m| and |n| mustn't exceed this (4-bit limit for |row|) */ @d maxq 255 /* $mn$ mustn't exceed this (8-bit |val| in |mv| codes) */ @d board(i,j) brd[(i)+m*(j)] @c #include #include int m,n; /* command-line parameters */ int q; /* the number of edges ($mn$) */ unsigned long long mems; /* memory accesses */ unsigned long long thresh=delta; /* time for next progress report */ unsigned long long nodes; /* nodes in the search tree */ unsigned long long leaves; /* nodes that have no descendants */ int count; /* number of solutions found so far */ int nonalf; /* number of non-alpha solutions found so far */ int brd[maxmn+maxmn]; /* one-dimensional array accessed via the |board| macro */ int rankl,rankr; /* how many rows of each part are active? */ int labeled[maxq+1]; /* what row and column, if any, have a particular label? */ int placed[maxq+1]; /* has this edge been placed? */ int move[maxq][1024]; /* feasible moves at each level */ int deg[maxq]; /* number of choices at each level; used in printouts only */ int x[maxq]; /* indexes of moves made at each level */ int vbose=0; /* can set this nonzero when debugging */ int left[maxmn],right[maxmn]; /* sorted solution */ @@; main (int argc,char*argv[]) { register int a,b,i,j,k,l,t,v,aa,bb,ii,row,col,ccol,val,mv,trouble; @; @; @; fprintf(stderr, "Altogether "O"d solution"O"s ("O"d alpha),", count,count==1?"":"s",count-nonalf); fprintf(stderr," "O"lld mems, "O"lld nodes, "O"lld leaves.\n", mems, nodes, leaves); } @ @= if (argc!=3 || sscanf(argv[1],""O"d",&m)!=1 || sscanf(argv[2],""O"d",&n)!=1) { fprintf(stderr,"Usage: "O"s m n\n",argv[0]); exit(-1); } if (m>maxmn || n>maxmn) { fprintf(stderr,"Sorry, m and n mustn't exceed "O"d!\n",maxmn); exit(-2); } if (m<2 || n<2) { fprintf(stderr,"Sorry, m and n should be 2 or more!\n"); exit(-4); } q=m*n; if (q>maxq) { fprintf(stderr,"Sorry, mn mustn't exceed "O"d!\n",maxq); exit(-3); } printf("--- Graceful labelings of K_{"O"d,"O"d} ---\n",m,n); @ The current status of the vertices labeled so far appears in the |board|, which has two columns, one for each part. This is not a canonical representation: The entries of each column can appear in any order. The first |rankl| rows of the first column, and the first |rankr| rows of the second column, have been labeled. When the vertex in row~$i$ and column~$j$ receives label~$l$, |labeled[l]| records the value |(j<<4)+i|; but |labeled[l]| is $-1$ if that label hasn't been used. If both endpoints of an edge are labeled, and if $d$ is the difference between those labels, |placed[d]=1|; but |placed[d]=0| if no edge for difference~|d| is yet known. @= rankl=rankr=0; for (l=0;l<=q;l++) labeled[l]=-1; l=0; @ @= void print_board(void) { register int i,j; for (i=0;i= void print_placed(void) { register int k; for (k=1;k<=q;k++) { if (placed[k]) { if (!placed[k-1]) fprintf(stderr," "O"d",k); else if (k==q || !placed[k+1]) fprintf(stderr,".."O"d",k); } } fprintf(stderr,"\n"); } @ These data structures are a bit fancy, so I'd better check that they're self-consistent. @d sanity_checking 1 /* set this to 1 if you suspect a bug */ @= void sanity(void) { register int i,j,l,t,v; @; @; @; } @ @= if (rankl>m) fprintf(stderr,"rankl shouldn't be "O"d!\n",rankl); if (rankr>n) fprintf(stderr,"rankr shouldn't be "O"d!\n",rankr); @ @= for (l=0;l<=q;l++) { v=labeled[l]; if (v>=0 && board(v&0xf,v>>4)!=l) fprintf(stderr,"labeled["O"d] not on the board!\n",l); } for (i=0;iq) fprintf(stderr,"board("O"d,"O"d) out of range!\n",i,0); if (labeled[board(i,0)]!=i) fprintf(stderr,"label of board("O"d,"O"d) is wrong!\n",i,0); } for (j=0;jq) fprintf(stderr,"board("O"d,"O"d) out of range!\n",j,1); if (labeled[board(j,1)]!=(1<<4)+j) fprintf(stderr,"label of board("O"d,"O"d) is wrong!\n",j,1); } @ @d testedge(i,j) if (!placed[abs(board(i,0)-board(j,1))]) fprintf(stderr,"edge from "O"d to "O"d not placed!\n", i,j); @= for (t=0,l=1;l<=q;l++) t+=placed[l]; if (t!=rankl*rankr) fprintf(stderr,"placement count is off ("O"d not "O"d)",t,rankl*rankr); for (i=0;i= enter: nodes++; if (mems>=thresh) { thresh+=delta; print_progress(l); } if (sanity_checking) sanity(); if (l<=1) @; if (l==q) @; if (o,placed[q-l]) @; for (t=a=0,b=q-l;b<=q;a++,b++) @; ready: deg[l]=t; /* no |mems| counted for diagnostics */ if (!t) leaves++; tryit:@+if (t==0) goto backup; advance:@+if (vbose) { fprintf(stderr,"L"O"d: ",l); print_move(move[l][t-1]); fprintf(stderr," ("O"d of "O"d)\n",deg[l]-t+1,deg[l]); } o,x[l]=--t; o,mv=move[l][t]; @; if (trouble) goto unmake; l++; goto enter; backup:@+if (--l>=0) { o,t=x[l]; unmake: o,mv=move[l][t]; @; goto tryit; } @ @= { count++; printf(""O"d: ",count); @; goto backup; } @ @= void print_progress(int level) { register int l,k,d,c,p; register double f,fd; fprintf(stderr," after "O"lld mems: "O"d sols,",mems,count); for (f=0.0,fd=1.0,l=0;l= { o,move[l][0]=0,t=1; goto ready; } @ @= void print_move(int mv) { if (!mv) fprintf(stderr,"null"); else if (mv<0x10000) fprintf(stderr,""O"d"O"d="O"d",(mv>>8)&0xf,(mv>>12)&0xf,mv&0xff); else fprintf(stderr,""O"d"O"d="O"d,"O"d"O"d="O"d", (mv>>8)&0xf,(mv>>12)&0xf,mv&0xff,(mv>>24)&0xf,(mv>>28)&0xf,(mv>>16)&0xff); } @# void print_moves(int level) { register int i; for (i=deg[level]-1;i>=0;i--) { /* we try the moves in decreasing order */ fprintf(stderr,""O"d:",deg[level]-i); print_move(move[level][i]); fprintf(stderr,"\n"); } } @ @= void print_state(int levels) { register int l; for (l=0;l= { if (l==0) o,move[0][0]=(pack(0,0,q)<<16)+pack(0,1,0),t=1; else if (m==n) o,move[1][0]=pack(1,1,1),t=1; else { o,move[1][0]=pack(1,1,1); o,move[1][1]=pack(1,0,q-1); t=2; } goto ready; } @ I set |trouble| nonzero if any edge is placed more than once. @= for (trouble=0;mv;mv>>=16) { val=mv&0xff,row=(mv>>8)&0xf,col=(mv>>12)&0xf; o,labeled[val]=(mv>>8)&0xff; o,board(row,col)=val; if (col==0) { if (row!=rankl) confusion("left move"); rankl++; for (j=0;j= void confusion(char *message) { fprintf(stderr,""O"s!\n",message); } @ @= if (mv>=0x10000) mv=(mv>>16)+((mv&0xffff)<<16); /* undo in opposite order */ for (;mv;mv>>=16) { val=mv&0xff,row=(mv>>8)&0xf,col=(mv>>12)&0xf; o,labeled[val]=-1; if (col==0) { rankl--; if (row!=rankl) confusion("left unmove"); for (j=0;j= { oo,aa=labeled[a],bb=labeled[b]; if (aa>=0) { if (bb>=0) continue; /* |a| and |b| are already on the |board| */ row=aa&0xf, col=aa>>4; @; }@+else if (bb>=0) { row=bb&0xf, col=bb>>4; @; } else @; } @ @= if (col==0 && right_legal(b)) o,move[l][t++]=pack(rankr,1,b); else if (col==1 && left_legal(b)) o,move[l][t++]=pack(rankl,0,b); @ @= int right_legal(val) { register int i,v; if (rankr==n) return 0; for (i=0;i= int left_legal(val) { register int j,v; if (rankl==m) return 0; for (j=0;j= if (col==0 && right_legal(a)) o,move[l][t++]=pack(rankr,1,a); else if (col==1 && left_legal(a)) o,move[l][t++]=pack(rankl,0,a); @ Finally, the hard case is when a double move is needed. First I tentatively try all placements of~|a|, actually changing the board. Then I record the double moves for |b| adjacent to every such placement. Of course the board has to be restored again. @= if (left_legal(a)) { aa=mv=pack(rankl,0,a);@+@;@+mv=aa; if (!trouble) @; @; } if (right_legal(a)) { aa=mv=pack(rankr,1,a);@+@;@+mv=aa; if (!trouble) @; @; } @ @= { if (col==0 && right_legal(b)) o,move[l][t++]=(pack(rankr,1,b)<<16)+mv; else if (col==1 && left_legal(b)) o,move[l][t++]=(pack(rankl,0,b)<<16)+mv; } @*Looking for patterns. Most of the solutions seem to be derivable in a simple way from smaller solutions. Namely, suppose the left part contains $mn=a_1>\ldots>a_m>0$ and the right part contains $0=b_1<\ldots1$, we can obtain two larger solutions: \item{1)} Replace each $a_i$ by $ta_i$ and each $b_j$ by $tb_j$, $tb_j+1$, \dots, $tb_j+t-1$. This is a graceful alpha solution for $K_{m,tn}$. \item{2)} Replace each $b_j$ by $tb_j$ and each $a_i$ by $ta_i$, $ta_i-1$, \dots, $ta_i-t+1$. This is graceful alpha solution for $K_{tm,n}$. I conjecture that all alpha solutions are obtained in this way. Equivalently, all alpha solutions can be reduced to a smaller alpha solution by inverting (1) or~(2). The following program marks a non-alpha solution with \.\#'. An alpha solution obtained from a smaller one by~(1) or~(1) is marked \.{L$t$}' or \.{R$t$}', respectively. An alpha solution not obtained by either (1) or~(2) is marked \.{XXX}'. @= @; for (i=0;i; @ @= for (i=0;i0;j--) { if (left[j-1]>a) break; left[j]=left[j-1]; } left[j]=a; } for (j=0;j0;i--) { if (right[i-1]= { for (t=1;;t++) if (t==m || left[t]!=q-t) break; if (t>1) { if (m@q)@>%t) goto irreducible; for (j=0;j%t) goto irreducible; for (v=t;v%t) goto irreducible; for (i=1;i1) { if (n@q)@>%t) goto irreducible; for (i=0;i%t) goto irreducible; for (v=t;v%t) goto irreducible; for (i=1;i