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

(Andrew Bayly) | (Andrew Bayly) |

(Jon Palin) |

(Jon Palin) | ||

(Jon Palin) | (George Sicherman) | (George Sicherman) |

(George Sicherman) | (George Sicherman) | (George Sicherman) |

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

n | labels | author |
---|---|---|

3 | 0, 9, 16 | |

4 | 0, 0, 9, 16 | |

5 | 0, 1, 15, 21, 4 | Andrew Bayly |

6 | 0, 0, 1, 15, 21, 4 | |

7 | 0, 0, 1, 3, 22, 27, 9 | |

8 | 0, 0, 1, 8, 8, 17, 32, 4 | |

9 | 0, 0, 1, 8, 8, 17, 32, 32, 4 | George Sicherman |

10 | 0, 0, 1, 8, 28, 21, 60, 61, 39, 25 | George Sicherman |

11 | 0, 0, 1, 8, 8, 28, 21, 60, 61, 39, 25 | George Sicherman |

12 | 0, 0, 1, 3, 6, 43, 38, 62, 59, 5, 11, 25 | George Sicherman |

13 | 0, 0, 1, 3, 6, 10, 39, 61, 3, 22, 59, 85, 36 | George Sicherman |

14 | 0, 0, 1, 3, 13, 51, 49, 32, 4, 5, 20, 101, 95, 49 | George Sicherman |

15 | 0, 0, 1, 3, 6, 10, 26, 38, 11, 14, 67, 33, 88, 56, 169 | George Sicherman |

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

n | center | others | author |
---|---|---|---|

4 | 2 | 3362, 359, 482 | Jon Palin |

5 | 194 | 962, 62, 2, 482 | Jon Palin |

6 | 224 | 1712, 137, 32, 452, 2912 | Jon Palin |

7 | 144 | 3456, 25, 0, 256, 585, 640 | Jon Palin |

8 | 144 | 880, 81, 0, 256, 585, 5040, 7956 | Jon Palin |

9 | 260 | 701, 140, 29, 1340, 2141, 6140, 101, 524 | Jon Palin |

10 | 482 | 962, 194, 2, 47, 1634, 1282, 9122, 3874, 887 | Jon Palin |

11 | 212 | 364, 77, 44, 317, 2492, 1997, 1724, 877, 3884, 1157 | Jon Palin |

12 | 8 | 136, 188, 1928, 281, 248, 3473, 1288, 5768, 161, 568, 953 | George Sicherman |

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

n | labels | author |
---|---|---|

2 | 0, 0, 9, 16 | |

3 | 0, 0, 9, 16, 153, 72, 49, 576 | George Sicherman |

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

n | labels | author |
---|---|---|

3 | 0, 9, 16 | |

4 | 2, 359, 482, 3362 | Jon Palin |

5 | 7442, 28658, 148583, 177458, 763442 | Jean-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.