Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/34815`

Title: | Hamiltonian circuits in trivalent planar graphs. |

Authors: | Price, W. L. |

Award date: | 1973 |

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

Links: | http://hdl.handle.net/2381/34815 |

Level: | Doctoral |

Qualification: | Ph.D. |

Rights: | Copyright © the author. All rights reserved. |

Appears in Collections: | Theses, Dept. of Engineering Leicester Theses |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

U323888.pdf | 3.19 MB | Adobe PDF | View/Open |

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.