Problem of the Month
(December 2008)

Given a graph, a collection of vertices and edges connecting them, we want to label the vertices so that the label of each vertex is the sum of the digits of the labels of the adjacent vertices. What graphs and labelings have this property?


ANSWERS

Any graph can be labeled with 0's. These labelings are trivial, and are omitted below.

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:

Paths
LengthLabelings
21, 1
2, 2
3, 3
4, 4
5, 5
6, 6
7, 7
8, 8
51, 10, 9, 17, 8
2, 11, 9, 16, 7
3, 12, 9, 15, 6
4, 13, 9, 14, 5
81, 10, 9, 17, 17, 9, 10, 1
2, 11, 9, 16, 16, 9, 11, 2
3, 12, 9, 15, 15, 9, 12, 2
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

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.

Cycles
LengthLabelings
46, 12, 6, 12
62, 10, 8, 16, 8, 10
3, 10, 7, 15, 8, 11
4, 10, 6, 14, 8, 12
4, 11, 7, 14, 7, 11
5, 10, 5, 13, 8, 13
5, 11, 6, 13, 7, 12
6, 12, 6, 12, 6, 12
9, 10, 10, 9, 17, 17
9, 11, 11, 9, 16, 16
9, 12, 12, 9, 15, 15
9, 13, 13, 9, 14, 14
17, 17, 18, 19, 19, 18
86, 12, 6, 12, 6, 12, 6, 12
106, 12, 6, 12, 6, 12, 6, 12, 6, 12

Regular Graphs
(and Complete Graphs)
DegreeLabelings
11
2
3
4
5
6
7
8
412
24
48
721 (Ed Pegg)
42 (Ed Pegg)
84 (Ed Pegg)
1010 (JD)
20 (JD)
30 (JD)
40 (JD)
50 (JD)
60 (JD)
70 (JD)
80 (JD)
11198 (JD)
13195 (JD)
16192 (JD)
288 (JD)
19114 (JD)
133 (JD)
152 (JD)
190 (JD)
209 (JD)
228 (JD)
247 (JD)
266 (JD)
285 (JD)
21378 (JD)
22132 (JD)

Complete Bipartite Graphs
m \ n123456789
11, 1
2, 2
3, 3
4, 4
5, 5
6, 6
7, 7
8, 8
        
2  6, 12       
3           
43, 12
6, 24
    12, 12
24, 24
48, 48
     
5  2, 10
4, 20
6, 30
8, 40
10, 5
12, 15
14, 25
16, 35
    15, 30    
6              
73, 21
6, 42
    12, 21
20, 14
24, 42
28, 70
32, 35
40, 28
44, 56
48, 84
52, 49
56, 77
68, 98
    21, 21
42, 42
84, 84
  
8  12, 24
24, 48
    30, 24
60, 48
75, 96
    32, 40
64, 80
88, 128
 
9         
101, 10
2, 20
3, 30
4, 40
5, 50
6, 60
7, 70
8, 80
   12, 30
24, 60
  21, 30
42, 60
  
1118, 99 (JD)12, 33
24, 66
36, 99
54, 9972, 9910, 11
20, 22
30, 33
40, 44
50, 55
60, 66
70, 77
80, 88
90, 99
108, 99126, 99144, 99
48, 132
96, 165
162, 99

Grids
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

Wheels
SizeCenterOther Labelings
51815, 21, 15, 21
61512, 12, 12, 12, 12
3015, 15, 15, 15, 15
72713, 20, 16, 23, 16, 20
14, 20, 15, 22, 16, 21
15, 21, 15, 21, 15, 21
3617, 20, 21, 19, 25, 24
17, 21, 22, 19, 24, 23
17, 22, 23, 19, 23, 22
18, 20, 20, 18, 25, 25
18, 21, 21, 18, 24, 24
18, 22, 22, 18, 23, 23
5425, 25, 27, 29, 29, 27
25, 26, 28, 29, 28, 26
26, 26, 27, 28, 28, 27
9810, 10, 10, 10, 10, 10, 10, 10
1611, 11, 11, 11, 11, 11, 11, 11
204, 10, 4, 10, 4 10, 4, 10
2412, 12, 12, 12, 12, 12, 12, 12
2814, 20, 14, 20, 14, 20, 14, 20
3213, 13, 13, 13, 13, 13, 13, 13
3615, 21, 15, 21, 15, 21, 15, 21
408, 20, 8, 20, 8, 20, 8, 20
14, 14, 14, 14, 14, 14, 14, 14
4416, 22, 16, 22, 16, 22, 16, 22
4818, 30, 18, 30, 18, 30, 18, 30
24, 24, 24, 24, 24, 24, 24, 24
5217, 23, 17, 23, 17, 23, 17, 23
5625, 25, 25, 25, 25, 25, 25, 25
6018, 24, 18, 24, 18, 24, 18, 24
6426, 26, 26, 26, 26, 26, 26, 26
8028, 28, 28, 28, 28, 28, 28, 28
114515, 21, 15, 21, 15, 21, 15, 21, 15, 21
123312, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12 (JD)

Bryce Herdt suggested investigating the smallest graph to have label n. He found that K11 has a labeling including 100, and K7 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 P2) whose labels have greatest common divisor n.

Smallest Known Graphs With At Least
3 Vertices Whose Labels Have GCD n
LabelSizeGraph
15P5
26C6
35P5
47K2,5
57K2,5
64C4
78pic (BH)
87K2,5
93P3
1011K11
1119pic (BH)
125K5
1315pic (BH)
148pic (BH)
156W6 (BH)
1612pic (BH)
1716pic (BH)
183C3
1924pic (BH)
2011K11

LabelSizeGraph
218K8
2216pic (BH)
2312pic (BH)
245K5
2512pic
2615pic (BH)
274K4
2822pic (JD)
2923pic (BH)
3011K11
3122pic (JD)
3214pic (BH)
3330hard (BH)
3416pic (BH)
3512pic (BH)
365K5
3719hard (BH)
3820pic (JD)
3915pic (BH)
4011K11

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.