Please use this identifier to cite or link to this item:
|Title:||Hamiltonian circuits in trivalent planar graphs.|
|Authors:||Price, W. L.|
|Presented at:||University of Leicester|
|Abstract:||The author has investigated the properties of Hamiltonian circuits in a class of trivalent planar graphs and he has attempted, with partial success, to establish conditions for the existence of Hamiltonian circuits in such graphs. Because the Hamiltonian circuits of a trivalent planar graph are related to the four-colourings of the graph some aspects of the four- colour problem are discussed. The author describes a colouring algorithm which extends the early work of Kempe, together with an algorithm based on the Heawood congruences which enables the parity of the number of four-colourings to be determined without necessarily generating all of the four-colourings. It is shown that the number of Hamiltonian circuits has the same parity as the number of four-colourings and that the number of Hamiltonian circuits which pass through any edge of a trivalent planar graph is either even or zero. A proof is given that the latter number is non-zero, for every edge of the graph, whenever the family of four-colourings has either of two stated properties. The author describes two original algorithms, independent of four-colourings, which generate a family of Hamiltonian circuits in a trivalent planar graph. One algorithm embodies a transformation procedure which enables a family of Hamiltonian circuits to be generated from a given Hamiltonian circuit, while the other generates directly all Hamiltonian circuits which include a chosen edge of the graph. In a new theorem the author proves the existence of Hamiltonian circuits in any trivalent planar graph whose property is that one or more members of a family of related graphs has odd parity.|
|Rights:||Copyright © the author. All rights reserved.|
|Appears in Collections:||Theses, Dept. of Engineering|
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.