logo

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

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.

VerticesConnectivityTotal
2345
0-400000
510001
600000
731004
800000
932101043
1011002
1113054101411730
122500025
Go to top

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.

VerticesGraphs
0-100
111
120
135
140
1540
160
17476
180
196808
Go to top

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


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close