(September 2012)

1. Given a graph, we can count how many ways there are to eliminate 1 vertex at a time (along with any incident edges) and keep the graph connected. For a given integer n, is there a graph that can be eliminated in exactly n ways, and if so, what is the smallest such graph?

2. If instead we eliminate edges one at a time, so as to not disconnect the graph (except for isolated vertices), what are the smallest graphs that can be eliminated in exactly n ways?

3. A Hamiltonian path is a path that visits all the vertices of a graph exactly once. For a given integer n, what is the smallest graph with exactly n Hamiltonian paths? We count a path and its reverse as the same path.

4. A Hamiltonian cycle is a cycle that visits all the vertices of a graph exactly once. For a given integer n, what is the smallest graph with exactly n Hamiltonian cycles? We count a cycle and all of its rotations and reflections as the same cycle.

Andrew Bayly found the vertex elimination number of complete graphs (v!), cycle graphs (v × 2^{v-2}), star graphs (2 × (v-1)!), and path graphs (2^{v-1}) with v vertices.

Andrew Bayly pointed out that all vertex elimination numbers are even, except 1. Joe DeVincentis pointed out that all graphs with 3 or more vertices that don't contain a triangle have vertex elimination numbers that are divisibly by 4.

Jon Palin used a computer program to search all connected graphs with 7 or fewer vertices. His results can be found here.

Here are the smallest graphs that can be vertex-eliminated in exactly n ways:

1 | 2 | 4 | 6 | 8 | 12 | 14 | 16 | 20 |

24 | 28 | 30 (JD) | 32 (AB) | 36 (JD) | 40 (JD) |

44 (JD) | 48 (JD) | 50 (JD) | 52 (JD) | 56 (JD) | 60 (JD) | 62 (JD) |

64 (AB) | 66 (JD) | 72 (JD) | 76 (JD) | 80 (JD) |

82 (JD) | 84 (JD) | 92 (JD) | 96 (JD) | 104 (JD) | 108 (JD) | 112 (JD) |

116 (JD) | 120 (JD) | 124 (JD) | 126 (JD) | 128 (JD) |

2.

Jeremy Galvagni found the edge elimination number of path graphs (2^{v-2}) with v vertices.

Joe DeVincentis found the edge elimination numbers of cycle graphs (v × 2^{v-2}) and star graphs ((v-1)!) with v vertices.

Here are the smallest known graphs that can be edge-eliminated in exactly n ways:

1 | 2 | 4 | 6 | 8 | 14 | 16 |

20 | 24 | 30 | 32 (JD) | 36 (JD) |

40 (JD) | 50 (JD) | 56 (JD) | 60 (JD) | 62 (JD) |

64 (JD) | 66 (JD) | 76 (JD) | 82 (JD) | 92 (JD) |

96 (JD) | 108 (JD) | 112 (JD) | 120 (JD) | 126 (JD) | 128 (JD) |

3.

Jeremy Galvagni found the Hamiltonian path number of complete graphs (v!/2) and cycle graphs (v) with v vertices.

Mark Mammel found the smallest graphs for n≤27 by computer.

Here are the smallest graphs that have exactly n Hamiltonian paths:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 (JG) |

9 (JG) | 10 (JG) | 11 (JG) | 12 (JG) | 13 (MM) | 14 (MM) | 15 (MM) |

16 (MM) | 17 (MM) | 18 (MM) | 19 (MM) | 20 (MM) | 21 (MM) |

22 (MM) | 23 (MM) | 24 (MM) | 25 (MM) | 26 (MM) | 27 (MM) | 28 (JT) |

29 (JT) | 30 (JT) | 31 (JT) | 32 (JT) | 33 (JT) | 34 (JT) |

35 (JT) | 36 (JT) | 37 (JT) | 38 (JT) | 39 (JT) | 40 (JT) |

41 (JT) | 42 (JT) | 43 (JT) | 44 (JT) | 45 (JT) | 46 (JT) |

47 (JT) | 48 (JT) | 49 (JT) | 50 (JT) | 51 (JT) | 52 (JT) |

53 (JT) | 54 (JT) | 55 (JT) | 56 (JT) | 57 (JT) | 58 (JT) |

59 (JT) | 60 (JT) | 61 (JT) | 62 (JT) | 63 (JT) | 64 (JT) |

65 (JT) | 66 (JT) | 67 (JT) | 68 (JT) | 69 (JT) | 70 (JT) |

71 (JT) | 72 (JT) | 73 (JT) | 74 (JT) | 75 (JT) | 76 (JT) |

77 (JT) | 78 (JT) | 79 (JT) | 80 (JT) | 81 (JT) | 82 (JT) |

83 (JT) | 84 (JT) | 85 (JT) | 86 (JT) | 87 (JT) | 88 (JT) |

89 (JT) | 90 (JT) | 91 (JT) | 92 (JT) | 93 (JT) | 94 (JT) |

95 (JT) | 96 (JT) | 97 (JT) | 98 (JT) | 99 (JT) | 100 (JT) |

4.

Jeremy Galvagni found the Hamiltonian cycle number of complete graphs ((v-1)!/2) with v vertices.

Andrew Bayly found that the wheel graph with v vertices has v-1 Hamiltonian cycles, so all positive integers are the Hamiltonian cycle number of some graph.

Mark Mammel found the smallest graphs for n≤25 by computer.

Jeremy Tan found the smallest graphs for 26≤n≤40 by computer. In 2014, he extended this to n≤88. He also computed that 7-vertex graphs can have these numbers of Hamiltonian cycles: 0-12, 14-20, 22-24, 26-28, 30, 32-34, 36, 38, 40, 45, 48, 52, 60, 62, 70, 72, 76, 80, 90, 108, 120, 144, 168, 240 and 360.

In 2018, Johan de Ruiter found that 8-vertex graphs can have these numbers of Hamilton cycles: 0-88, 90, 92-106, 108-116, 118, 120, 122-124, 126, 128-136, 138-140, 142, 144-150, 152-153, 156, 158, 160, 162, 164-166, 168-169, 172, 174, 176-177, 180, 183-184, 186, 188, 192, 194, 198, 200, 204, 208, 210, 212, 214, 216, 219-220, 222-223, 228, 230-232, 240, 245, 248, 252, 260, 264, 266, 268, 270, 276, 284, 292, 296, 298, 300, 308, 310, 312, 320, 323-324, 328, 336, 340, 348, 354, 360, 366, 384, 390, 408, 430, 432, 444, 456, 458, 476, 496, 504, 508, 576, 582, 636, 660, 696, 720, 744, 816, 912, 984, 1200, 1320, 1800, 2520. He also sent lists for n=9 and n=10.

Here are the smallest known graphs that have exactly n Hamiltonian cycles:

0 | 1 | 2 | 3 | 4 (AB) | 5 (MM) | 6 (MM) | 7 (MM) | 8 (MM) |

9 (MM) | 10 (MM) | 11 (MM) | 12 (MM) | 13 (MM) | 14 (MM) |

15 (MM) | 16 (MM) | 17 (MM) | 18 (MM) | 19 (MM) | 20 (MM) |

21 (MM) | 22 (MM) | 23 (MM) | 24 (MM) | 25 (MM) |

26 (JT) | 27 (JT) | 28 (JT) | 29 (JT) | 30 (JT) |

31 (JT) | 32 (JT) | 33 (JT) | 34 (JT) | 35 (JT) |

36 (JT) | 37 (JT) | 38 (JT) | 39 (JT) | 40 (JT) |

41 (JT) | 42 (JT) | 43 (JT) | 44 (JT) | 45 (JT) |

46 (JT) | 47 (JT) | 48 (JT) | 49 (JT) | 50 (JT) |

51 (JT) | 52 (JT) | 53 (JT) | 54 (JT) | 55 (JT) |

56 (JT) | 57 (JT) | 58 (JT) | 59 (JT) | 60 (JT) |

61 (JT) | 62 (JT) | 63 (JT) | 64 (JT) | 65 (JT) |

66 (JT) | 67 (JT) | 68 (JT) | 69 (JT) | 70 (JT) |

71 (JT) | 72 (JT) | 73 (JT) | 74 (JT) | 75 (JT) |

76 (JT) | 77 (JT) | 78 (JT) | 79 (JT) | 80 (JT) |

81 (JT) | 82 (JT) | 83 (JT) | 84 (JT) | 85 (JT) |

86 (JT) | 87 (JT) | 88 (JT) | 89 (JT) | 90 (JT) |

91 (JT) | 92 (JT) | 93 (JT) | 94 (JT) | 95 (JT) |

96 (JT) | 97 (JT) | 98 (JT) | 99 (JT) | 100 (JT) |

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