Problem of the Month (December 2011)

Given a planar graph with no endpoints, what are the smallest non-negative labels the vertices can have so that all the inherited edge labels (which are the sum of the labels of the two vertices they connect) are different squares?

Here smallest means minimal total, and among those, minimal maximum vertex label.


ANSWERS

Below are some graphs with 9 or fewer edges, and the smallest known vertex labelings. Can you improve any of these? Can you find any graphs i missed?

3 Edges

4 Edges

5 Edges

(Andrew Bayly)

(Andrew Bayly)

6 Edges

(Jon Palin)

7 Edges

8 Edges

(Jon Palin)

9 Edges

(Jon Palin)

(George Sicherman)

(George Sicherman)

(George Sicherman)

(George Sicherman)

(George Sicherman)

The smallest labels for cycles with n vertices are shown below:

Smallest Cycle Graphs with n Vertices
nlabelsauthor
30, 9, 16
40, 0, 9, 16
50, 1, 15, 21, 4Andrew Bayly
60, 0, 1, 15, 21, 4
70, 0, 1, 3, 22, 27, 9
80, 0, 1, 8, 8, 17, 32, 4
90, 0, 1, 8, 8, 17, 32, 32, 4George Sicherman
100, 0, 1, 8, 28, 21, 60, 61, 39, 25George Sicherman
110, 0, 1, 8, 8, 28, 21, 60, 61, 39, 25George Sicherman
120, 0, 1, 3, 6, 43, 38, 62, 59, 5, 11, 25George Sicherman
130, 0, 1, 3, 6, 10, 39, 61, 3, 22, 59, 85, 36George Sicherman
140, 0, 1, 3, 13, 51, 49, 32, 4, 5, 20, 101, 95, 49George Sicherman
150, 0, 1, 3, 6, 10, 26, 38, 11, 14, 67, 33, 88, 56, 169George Sicherman

The smallest labels for wheels with n vertices are shown below:

Smallest Wheel Graphs with n Vertices
ncenterothersauthor
423362, 359, 482Jon Palin
5194962, 62, 2, 482Jon Palin
62241712, 137, 32, 452, 2912Jon Palin
71443456, 25, 0, 256, 585, 640Jon Palin
8144880, 81, 0, 256, 585, 5040, 7956Jon Palin
9260701, 140, 29, 1340, 2141, 6140, 101, 524Jon Palin
10482962, 194, 2, 47, 1634, 1282, 9122, 3874, 887Jon Palin
11212364, 77, 44, 317, 2492, 1997, 1724, 877, 3884, 1157Jon Palin
128136, 188, 1928, 281, 248, 3473, 1288, 5768, 161, 568, 953George Sicherman

The smallest labels for n-dimensional cubes are shown below:

Smallest n-Dimensional Cube Graphs
nlabelsauthor
20, 0, 9, 16
30, 0, 9, 16, 153, 72, 49, 576George Sicherman

The smallest labels for complete graphs on n vertices are shown below:

Smallest Complete Graphs with n Vertices
nlabelsauthor
30, 9, 16
42, 359, 482, 3362Jon Palin
57442, 28658, 148583, 177458, 763442Jean-Louis Nicolas

What are the smallest vertex labelings of some other infinite families of graphs?


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