Recognizing binary Hamming graphs inO(n 2 logn) time

Aurenhammer, F., and Hagauer, J. Computing equivalence classes among the edges of a graph with applications.Discrete Math. 109 (1992), 3?12.

Brandenburg, L. H., Gopinath, B., and Kurshan, R. P. On the addressing problem of loop switching.Bell Systems Tech. J. 51 (1972), 1445?1469.

Djokovic, D. Z. Distance-preserving subgraphs of hypercubes.J. Combin. Theory Ser. B 14 (1973), 263?267.

Garey, M. R., and Graham, R. L. On cubical graphs.J. Combin. Theory Ser. B 18 (1975), 84?95.

Gilbert, E. N. Gray codes and paths on then-cube.Bell Systems Tech. J. 37 (1958), 1?12.

Graham, R. L., and Pollak, H. O. On the addressing problem for loop switching.Bell Systems Tech. J. 50 (1971), 2495?2519.

Graham, R. L., and Pollak, H. O. On embedding graphs in squashed cubes, In: Y. Alaviet al. (eds),Graph Theory and Applications. Lecture Notes in Mathematics, Vol. 303. Springer-Verlag, Berlin, 1972, pp. 99?110.

Gropp, W. D., and Ipsen, I. C. F. Recursive mesh refinement on hypercubes.BIT 29 (1989), 186?211.

Hong, J. W., Mehlhorn, K., and Rosenberg, A. L. Cost trade-offs in graph embeddings, with. applications.J. Assoc. Comput. Mach. 30 (1983), 709?728.

Wilkeit, E. Isometric embeddings in Hamming graphs.J. Combin. Theory Ser. B 50 (1990), 179?197.

Winkler, P. M. Isometric embedding in products of complete graphs.Discrete Appl. Math. 7 (1984), 221?225.

Wu, A. Y. Embedding of tree networks into hypercubes.J. Parallel Distrib. Comput. 2 (1985), 238?249.