Premium
An Algorithm which Generates the Hamiltonian Circuits of a Cubic Planar Map
Author(s) -
Price W. L.
Publication year - 1978
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-18.2.193
Subject(s) - planar , hamiltonian (control theory) , electronic circuit , algorithm , mathematics , hamiltonian path , topology (electrical circuits) , computer science , discrete mathematics , combinatorics , physics , mathematical optimization , graph , quantum mechanics , computer graphics (images)
The paper describes an algorithm which generates those Hamiltonian circuits of a given cubic planar map which include some chosen edge of the map. A simple extension of the method results in the generation of all the Hamiltonian circuits of the map. The algorithm can readily be implemented on a digital computer, subject to limitations on storage. A general property of the generating function defined by the algorithm leads to a proof that the total number of Hamiltonian circuits which include any given edge of a cubic planar map is even. Does the structure of the function yield further information concerning the properties of the family of Hamiltonian circuits?