Many early references to Golomb rulers, in other terminologies, have come to light. The earliest known to me is a problem by Henry D. Friedman that appeared in the SIAM Review, Vol. 5, July 1963, page 275.

Golomb rulers have practical applications to pulsed radar and sonar codes (see "Synch-Sets: A Variant of Difference Sets," by G. J. Simmons, Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing, Boca Raton, 1974, pages 625-645) and to X-ray diffraction crystallography. Two Golomb rulers of length 17 provide counterexamples to a "theorem" published by S. Picard in 1939 and used in crystallography for many years.

Richard Guy reported (The American Mathematical Monthly, Vol. 88, December 1981, page 756) that since Golomb revived Ringel's conjecture that all tree graphs are graceful, some 100 papers have dealt with partial results on this notorious and still unanswered question.

Ronald L. Graham and Neil Sloane, both of Bell Laboratories, have defined a "harmonious graph" as follows: A connected graph, with n edges, is harmonious if its points can be labeled with distinct integers (modulo n) so that the sums of the pairs of numbers at the ends of each edge are also distinct (modulo n). Harmonious graphs have much in common with graceful graphs, and are related to error-correcting codes and to a famous combinatorial problem known as the postage stamp problem. See "On Additive Bases and Harmonious Graphs," by Graham and Sloane, SIAM Journal on Algebraic and Discrete Methods, Vol. 1, December 1980, pages 382-404. The authors show (among many other things) that graphs known as ladders, fans, and wheels are harmonious. Trees (with zero repeated once) may be harmonious. The Petersen graph and skeletons of the tetrahedron, dodecahedron, and icosahedron are harmonious. Skeletons of the cube and octahedron are not. Almost all graphs, the authors conclude, are neither harmonious nor graceful.

In recent years Golomb and Herbert Taylor have been exploring a two-dimensional analog of ruler problems which have many practical applications. See their paper on "Two-dimensional Synchronization Patterns for Minimum Ambiguity," in IEEE Transactions on Information Theory, Vol. IT—28, July 1982, pages 600-604, and Golomb's "Algebraic Constructions for Costas Arrays," to appear in Journal of Combinatorial Theory, Series A, sometime in 1983.

0 0

Post a comment