Perihamiltonian graphs

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:

Perihamiltonian graphs

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

Perihamiltonian 3-connected plane graphs

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

References

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