A graph G is *perihamiltonian* if G is non-hamiltonian yet every edge-contracted subgraph of G is hamiltonian (see [1] for more details).

The following lists are available:

The following table gives the complete lists of all perihamiltonian graphs with a given connectivity. These graphs were generated using the program geng and were filtered using the program multi_is_perihamiltonian. The graphs are available in 'graph6' format.

Vertices | Connectivity | Total | |||
---|---|---|---|---|---|

2 | 3 | 4 | 5 | ||

0-4 | 0 | 0 | 0 | 0 | 0 |

5 | 1 | 0 | 0 | 0 | 1 |

6 | 0 | 0 | 0 | 0 | 0 |

7 | 3 | 1 | 0 | 0 | 4 |

8 | 0 | 0 | 0 | 0 | 0 |

9 | 32 | 10 | 1 | 0 | 43 |

10 | 1 | 1 | 0 | 0 | 2 |

11 | 1305 | 410 | 14 | 1 | 1730 |

12 | 25 | 0 | 0 | 0 | 25 |

The following table gives the complete lists of all perihamiltonian 3-connected plane graphs. These graphs were generated using the program plantri and were filtered using the program multi_is_perihamiltonian. The graphs are available in 'planar_code' format.

Vertices | graphs |
---|---|

0-10 | 0 |

11 | 1 |

12 | 0 |

13 | 5 |

14 | 0 |

15 | 40 |

16 | 0 |

17 | 476 |

18 | 0 |

19 | 6808 |

[1] I. Fabrici, T. Madaras, M. Timková, N. Van Cleemput, and C.T. Zamfirescu, Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian, submitted, 2019.