Any graph whose vertices have degrees 10 or less can be labeled: label each vertex with 9 times its degree. We therefore consider these labelings trivial and omit them below. In fact, Joe DeVincentis pointed out this is true as long as all the degrees d of the graph have the property that 9d has digit sum 9.

Here are some of the small digit sum graphs:

In 2011, the Marin Math Circle discovered that these patterns likely continue. Only for n = 2 (mod 3) are there solutions, and these solutions are symmetric for even n and asymmetric for odd n.

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

1 10 9 17 8   2 11 9 16 7   3 12 9 15 6   4 13 9 14 5

1 10 9 17 17 9 10 1   2 11 9 16 16 9 11 2

3 12 9 15 15 9 12 3   4 13 9 14 14 9 13 4

5 14 9 13 13 9 14 5   6 15 9 12 12 9 15 6

7 16 9 11 11 9 16 7   8 17 9 10 10 9 17 8

8 17 18 19 19 18 17 8

10 18 26 18 10   11 18 25 18 11   12 18 24 18 12
10 18 26 18 10   11 18 25 18 11   12 18 24 18 12

13 18 23 18 13   14 18 22 18 14   15 18 21 18 15
13 18 23 18 13   14 18 22 18 14   15 18 21 18 15

16 18 20 18 16   16 27 29 27 16   17 27 28 27 17
16 18 20 18 16   16 27 29 27 16   17 27 28 27 17

19 27 26 27 19
19 27 26 27 19

10 14 14 10   12 15 15 12   14 16 16 14
14 26 26 14   15 24 24 15   16 22 22 16
14 26 26 14   15 24 24 15   16 22 22 16
10 14 14 10   12 15 15 12   14 16 16 14

16 17 17 16   16 26 26 16   20 19 19 20
17 20 20 17   26 38 38 26   19 34 34 19
17 20 20 17   26 38 38 26   19 34 34 19
16 17 17 16   16 26 26 16   20 19 19 20

Bryce Herdt suggested investigating the smallest graph to have label n. He found that K₁₁ has a labeling including 100, and K₇ has a labeling including 108. It turns out this problem is fairly easy for all n with digit sum 9 or less. Connect n to its digital sum s and several copies of 9, each of which is connected connected to the same copy of (18–s), which in turn is connected to (9–s). If n has digit sum between 9 and 18, then connect n to s and a bunch of copies of 18, each of which is connected to (27–s), which in turn is connected to (18–s).

Bryce Herdt also suggested investigating the smallest graph whose labels are the first n positive integers, or in different bases, or both! He gave an example in base 2:

Bryce Herdt also suggested investigating the smallest graph (besides P₂) whose labels have greatest common divisor n.

Joe DeVincentis wondered whether ALL graphs have these digit sum labelings.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/3/11.