Kevin's Math Page

# Graceful Graphs

 Click here for PDF version.   Background Graceful graphs are the creation of Solomon W. Golomb, professor of electrical engineering and mathematics at the University of Southern California. A graceful graph is a graph of points and connecting lines which can be numbered in a certain way. Let us say the graph has p points and e lines (e for edges) connecting them. Each of the points is assigned an integer. Each of the lines is labeled with the difference between the two integers of the points which it connects. Then, if the numbers corresponding with the lines run from 0 through e, then the graph is said to be graceful. See Figure B-1 for an example of a graceful graph. Let us take a special case of graphs in which every point is connected to every other point. These graphs, some of which are shown in Figure B-2A, are called complete graphs. These special graphs may be viewed in a less abstract way as follows: Form a ruler with p different divisions, each division corresponding to a number on the graph. See Figure B-2B for examples. Such graphs where the ruler can measure each of, but only, the distances from 0 through the length of the ruler are called perfect Golomb rulers. There are no perfect Golomb rulers with more than 4 divisions (proof is shown in the folder). Golomb rulers with more than 4 divisions (not perfect Golomb rulers) are those which measure unique lengths. In other words, the ruler in Figure B-3A is a Golomb ruler, but the one in Figure B-3B is not. Throughout this project, a ruler is represented by a sequence of numbers. Each number represents the length of a division on a ruler. For example, see Figure B-4, which shows the ruler 1, 3, 5, 2. Purpose By selecting a long enough ruler and dividing it in the right way, it is fairly easy to construct a Golomb ruler. The purpose of this project, therefore, is to find a way of constructing the shortest possible Golomb rulers. For example, Figure 1-A shows a Golomb ruler with 6 divisions. It is not, however, the shortest such ruler. Figure 1-B displays the shortest possible 6-division Golomb rulers. We want to find a way of finding the shortest possible Golomb rulers for any number of divisions. Hypothesis Previous searches have revealed minimum-length Golomb rulers for up to 12 divisions. These are shown in Figure 2. At first glance, the lengths have no apparent pattern to them: 3, 6, 11, 17, 25, 34, 44, 55, 72, 85, 106. Upon further staring, nothing clicks. This is not a simple problem. To begin with, as stated before, there are no perfect Golomb rulers with more than 4 divisions. Let us analyze these impossible Golomb rulers. A Golomb ruler with p divisions measures a certain number of distances, as shown in Figure 3. A pattern is easily seen: 1, 3, 6, 10, 15, etc. The differences between these numbers is 1, 2, 3, 4, 5. So these numbers are simply the sum of the numbers 1 through p . This is commonly-known (among mathematicians, at least) as (p)(p+1)/2 . A proof is shown in the folder. In any case, the point is that these (1, 3, 6, 10, 15, etc.) would be the lengths of the rulers if all Golomb rulers were perfect Golomb rulers. A non-perfect Golomb ruler, since it must - by definition - measure unique distances, must have a size greater than 1, 3, 6, etc. (depending on its number of divisions). The actual lengths 3, 6, 11, 17, 25... are very close to the perfect series 3, 6, 10, 15, 21. In fact, the differences are 0, 0, 1, 2, 4, 6, 8, 10, 17, 19, 28. Still, however, no pattern is easily recognizable. People jokingly say scientists either change data to fit their hypothesis or change their hypothesis to fit the data. Having looked for a clue to a solution and having found none, I won't hazard an unfounded guess. Methods To help in the search for a method of developing Golomb rulers, I began to write a series of computer programs in the C programming language for the Apple Macintosh. All of these programs are listed separately in the folder. While I was working on these programs, I also began looking into establishing upper and lower bounds for the lengths of Golomb rulers. The search is documented more completely in the folder. A few proofs for the non-existence of certain rulers are also shown in the folder. The main problem in writing the computer programs was that much attention had to be given to speed. At first, the time factor was not known. After the bugs were worked out of the program and the program was tested, however, it was clear that the program would be of almost no use in its present form. So the program had to be completely revamped - one whole section of it completely rewritten - and then debugged yet again. Even after a speed increase of at least 10 times, the program was still too slow to provide much useful information. So the program was modified to skip certain sets of numbers. A different modification let the user enter the numbers to check. The modified program was then stripped to the bone so that it only checked for Golombicity (whether or not it's a Golomb ruler) for one user-entered ruler. Still another program averaged the division lengths in certain positions of a Golomb ruler. For example, if the program found two rulers, 1 3 5 2 and 2 5 1 3, then the average of those two rulers would be 1.5 4 3 2.5. The purpose of this was to hopefully provide information on the general structure of Golomb rulers. Results All of the results from the computer programs are listed in the folder. The listings were analyzed and different theories were tested, but most failed. The folder contains several proofs concerning Golomb rulers. There is a proof that there are no perfect Golomb rulers with more than 4 divisions. There is a proof that there are no Golomb rulers with more than 6 divisions which have a length of (p(p+1)/2)+1 , where p is the number of divisions. That is the highest the lower bound was computed to. Clearly, a ruler with divisions of lengths 1, 2, 4, 8, 16, etc. is a Golomb ruler. A formal proof is shown in the folder. Also, a ruler such as 1, 2, 4, 5 or 1, 2, 4, 8, 9 is Golomb (proof also shown). So the upper bound was lowered to 2p-1 + 2p-2. This was clearly a terrible upper bound. The best method - by far - that I could find of constructing Golomb rulers is what I call the Middle Number Method. After looking at the different Golomb rulers, it seemed as if many followed a similar pattern. The numbers are almost in numerical order if we count in this manner: left, right, left, right, beginning on the outside and ending up in the middle. For example, the ruler 1 3 6 5 2 would be read 1, 2, 3, 5, 6. The Middle Number Method starts with a Golomb ruler with 3 divisions, such as 1 3 2, and tries to find a number larger than any of the others to place in the middle so that the ruler remains Golomb. If we start with 1 3 2, then the rulers continue 1 3 5 2, and 1 3 6 5 2 and 1 3 6 8 5 2 and so on. A proof that the Middle Number Method works (that there always exists such a number to place in the middle) is located in the folder. The listing of a computer program to find these rulers is also in the folder. All of the lower and upper bounds are shown in Figure 4, along with the results from the Middle Number Method. Observations As expected, there are more Golomb rulers with longer lengths. This isn't simply because there are more rulers (although that is part of the reason); the greater length means that the division lengths are more distinct. For example, if we have a ruler with division lengths of 1, 2, 3, and 27, then the 27 portion can be placed anywhere in the ruler and not change the Golombicity of the ruler. On the other hand, if the ruler had lengths 1, 2, 3, 5 then the 5 portion is restrictive to the ruler because the 2 cannot be placed next to the 3. It would seem that if we start the Middle Number Method with a longer 3-division ruler, then all of the resulting lengths would be longer. This is not the case. For up to about 25 divisions, it holds true. However, using 1 3 2 as our beginning ruler the 36-division ruler is 3182 units long, whereas with the 1 4 3 beginning ruler the 36-division ruler is 3134 units long. And the difference gets larger for larger rulers. For 40 divisions the difference is 4490 to 4264. As far as the averaging data goes, it appears that smaller rulers are more distinct, while larger rulers are very different, causing the average ruler to look very dull - as in 2 5 5 5 5 in one case. Figure 5 compares the different average-ruler results. Due to a feature of the program, only rulers in which the first division is shorter than the last will the ruler be counted as Golomb. For example, it will count 1 3 5 2 but not 2 5 3 1. In this manner, mirror-images are not counted as two, but it also forces the average of the last division to be at least 2. Conclusions I failed to find a method of constructing the shortest possible Golomb rulers. I did, however, find an algorithm for constructing Golomb rulers of any number of divisions - the Middle Number Method. Also, I created a lower bound for the lengths of Golomb rulers. This will be helpful in the search, as it will avoid wasting time looking for non-existent Golomb rulers. Proof_machine.c, still being programmed, should provide a quick way of proving the non-existence of certain Golomb rulers and possibly provide a way of raising the lower bound. A preliminary listing is located in the folder. Finally, further analysis of the results of the programs used in this project, along with more running time on a faster computer (perhaps a rented Macintosh II), and a little luck should provide even shorter Golomb rulers than the shortest ones known at this time. Significance The following is an excerpt from a Scientific American article dealing with Golomb rulers (see folder for complete article). Radio astronomy makes occasional use of Golomb rulers in the resolution of distant radio sources and in the measurement of our own planet. In the first case a number of antennas are placed along a straight line several kilometers long. The antenna positions correspond to the marks on a Golomb ruler. To locate a distant radio source, it is essential to determine the angle between the antenna baseline and the direction of the wave fronts arriving from the source. The antennas are all observing at a given wavelength. The precise time at which each wave in the incoming signal arrived at each antenna can be determined by analysis of the tape that captures the incoming signal. The total number of wavelengths between a given pair of antennas is called the total phase difference. It is normally composed of an integer and a fractional part called the phase difference. If the total phase difference can be reconstructed, the sought-for angle between the source and the baseline is easily calculated from the observing wavelength and c , the speed of light. Each pair of antennas, however, can only yield the phase difference itself, not the total phase difference. In truth, it is Fourier analysis that recaptures the total phase difference from the many pairs of antenna recordings. But if the distance between one pair of antennas is the same or nearly the same as the distance between another pair, the two pairs provide the same phase-difference information. Redundancy of information means its loss. The accuracy of the source-angle computation is greatest if each antenna pair records a different phase difference; this condition is achieved by in effect placing the antennas on the marks of a Golomb ruler. Okay, so if you didn't get all that mumbo-jumbo, in essence this is what it says: if radio antenna are placed on the marks of a Golomb ruler, then they get more accurate results. So the search for Golomb rulers does have significance. Possible Extensions There are several possible extensions to this project. To begin with, this project deals only with Golomb rulers. This is only a scratch on the surface of graceful graphs. This project could explore the properties of graceful graphs. Is it possible to tell if a graph is graceful simply by looking at it? A different approach to the Golomb ruler problem could be pursued. Instead of using a constant number of divisions and searching for the shortest length, we could start with a constant length and see how many divisions (and of what length) we need so that we can measure every length from 1 to the length of the ruler. These would not be Golomb rulers, as they would measure some distances more than once. But the problem would be of a similar nature. Finally, Sophie Piccard, a Swiss mathematician, in 1939 propounded a "theorem" stating that two rulers measuring the same set of distinct distances must be the same rulers. The theorem fails for 5 divisions. The theorem has not been disproven for longer rulers. I have begun work on a computer program to find such a ruler, but as yet have not completed it. A preliminary listing of the program is located in the folder.

Kevin's Math Page