Skip to content
No description, website, or topics provided.
C Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.

Perihamiltonian graphs

Program to check graphs for being perihamiltonian. A graph is perihamiltonian if it is not hamiltonian, but every edge-contracted subgraph is hamiltonian. This class is a proper superclass of hypohamiltonian and almost hypohamiltonian graphs. Theoretical results about this class can be found in 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.

This program was tested against an independent implementation written in Mathematica for all graphs on up to 10 vertices. It was also tested for larger graphs for which the perihamiltonicity had been determined theoretically.

You can’t perform that action at this time.