(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) |

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. 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.

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.