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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:737226 |
| Date | January 1973 |
| Creators | Price, W. L. |
| Publisher | University of Leicester |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/2381/34815 |
Page generated in 0.0132 seconds