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.