The subject of the thesis belongs to the theory of graphs. In 1966, C. St. J.A. Nash-Williams conjectured that the square of a block is hamiltonian. This conjecture quickly gained a wide popularity and, at the end of 1970, it was established by H. Fleischner. His proof of the existence of a hamiltonian cycle in the square of a block does not explicitly provide an algorithm for finding the cycle. The thesis will describe such an algorithm, with a running time O(n('2)) on every input with n vertices. For the most part, our algorithm follows closely the original lines of Fleischner's proof. The main difference occurs at the part where Fleischner proves the existence of a certain spanning subgraph in every connected bridgeless graph: we replace Fleischner's argument by a radically different one. This is the main original result of our thesis.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.68500 |
| Date | January 1980 |
| Creators | Lau, H. T. (Hang Tong), 1952- |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 000089124, proquestno: AAINK50482, Theses scanned by UMI/ProQuest. |
Page generated in 0.0018 seconds