Answers

Solutions to the six graphs that readers were asked to number "gracefully" are shown in Figure 103. None of these number-ings is unique.

Readers were also asked to improve on the rows of "Go-lomb's triangle," each row giving the shortest-known rulers of n marks (including end points) such that every distance between a pair of marks is a distinct integer. Walter Penney of Greenbelt, Md., was the first to lower the eight-mark ruler to length 34. The same ruler was also found by hand by Daniel A. Lynch of Wildwood, N.J.

William Mixon of the University of Chicago was the first to make an exhaustive computer search for all minimum-length rulers through 11 marks. His results show that rulers of eight, nine and 10 marks are unique, except of course for reversals [see Figure 104]. These results were completely confirmed by Ashok Kumar Chandra's computer program at Stanford University and partly confirmed by the programs of Paul Steier, James R. Van Zandt, Edward Schonberg and others. Working by hand, Sheldon B. Akers found the nine-mark ruler, and

NODES

LENGTH

DIVISIONS

3

3

1, 2

4

6

1, 3, 2

2, 5, 1, 3

6

17

1, 3, 6, 2, 5 1, 3, 6, 5, 2 1, 7, 3, 2, 4 1, 7, 4, 2, 3

7

25

2, 1, 7, 6, 5, 4 2, 5, 6, 8, 1, 3

8

34

1, 3, 5, 6, 7, 10, 2

9

44

1, 4, 7, 13, 2, 8, 6, 3

10

55

1, 5, 4, 13, 3, 8, 7, 12, 2

11

72

1, 3, 9, 15, 5, 14, 7, 10, 6, 2 1, 8, 10, 5, 7, 21, 4, 2, 11, 3

Minimum-length Golomb rulers

Minimum-length Golomb rulers

Wolfgang Harries, also working by hand, found all but one of the rulers with six and seven marks.

The 10-mark ruler and one 11-mark ruler had been found earlier by John P. Robinson of the University of Iowa with a nonexhaustive computer search made in connection with work on his 1966 doctorate on error-correcting codes. His best results, for rulers through 24 marks, are given in "A Class of Binary Recurrent Codes with Limited Error Propagation," by Robinson and Arthur J. Bernstein, in IEEE Transactions on Information Theory (Volume IT-13, Number 1, January, 1967, pages 106—113).

R. C. Ashenfelter of the Bell Telephone Laboratories was the first to gracefully label the dodecahedron. Chandra devised a computer program that made an exhaustive search for the icosahedron and produced five fundamentally different label-ings. A partial search for the dodecahedron yielded a large number of graceful labelings. This settles affirmatively Go-lomb's conjecture that the skeletons of all five Platonic solids are graceful graphs.

0 0

Post a comment