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 × 2v-2), star graphs (2 × (v-1)!), and path graphs (2v-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) |
Jeremy Galvagni found the edge elimination number of path graphs (2v-2) with v vertices.
Joe DeVincentis found the edge elimination numbers of cycle graphs (v × 2v-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) |
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) |
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≤34.
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) |
If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 10/28/12.