Hamiltonian cycles in maximal planar graphs and planar triangulations

Simple item page
dc.contributor.advisorErwin, Daviden_ZA
dc.contributor.authorMofokeng, Tshenoloen_ZA
dc.date.accessioned2017-09-26T14:50:09Z
dc.date.available2017-09-26T14:50:09Z
dc.date.issued2017en_ZA
dc.description.abstractIn this thesis we study planar graphs, in particular, maximal planar graphs and general planar triangulations. In Chapter 1 we present the terminology and notations that will be used throughout the thesis and review some elementary results on graphs that we shall need. In Chapter 2 we study the fundamentals of planarity, since it is the cornerstone of this thesis. We begin with the famous Euler's Formula which will be used in many of our results. Then we discuss another famous theorem in graph theory, the Four Colour Theorem. Lastly, we discuss Kuratowski's Theorem, which gives a characterization of planar graphs. In Chapter 3 we discuss general properties of a maximal planar graph, G particularly concerning connectivity. First we discuss maximal planar graphs with minimum degree i, for i = 3; 4; 5, and the subgraph induced by the vertices of G with the same degree. Finally we discuss the connectivity of G, a maximal planar graph with minimum degree i. Chapter 4 will be devoted to Hamiltonian cycles in maximal planar graphs. We discuss the existence of Hamiltonian cycles in maximal planar graphs. Whitney proved that any maximal planar graph without a separating triangle is Hamiltonian, where a separating triangle is a triangle such that its removal disconnects the graph. Chen then extended Whitney's results and allowed for one separating triangle and showed that the graph is still Hamiltonian. Helden also extended Chen's result and allowed for two separating triangles and showed that the graph is still Hamiltonian. G. Helden and O. Vieten went further and allowed for three separating triangles and showed that the graph is still Hamiltonian. In the second section we discuss the question by Hakimi and Schmeichel: what is the number of cycles of length p that a maximal planar graph on n vertices could have in terms of n? Then in the last section we discuss the question by Hakimi, Schmeichel and Thomassen: what is the minimum number of Hamiltonian cycles that a maximal planar graph on n vertices could have, in terms of n? In Chapter 5, we look at general planar triangulations. Note that every maximal planar graph on n ≥ 3 vertices is a planar triangulation. In the first section we discuss general properties of planar triangulations and then end with Hamiltonian cycles in planar triangulations.en_ZA
dc.identifier.apacitationMofokeng, T. (2017). <i>Hamiltonian cycles in maximal planar graphs and planar triangulations</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/25389en_ZA
dc.identifier.chicagocitationMofokeng, Tshenolo. <i>"Hamiltonian cycles in maximal planar graphs and planar triangulations."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2017. http://hdl.handle.net/11427/25389en_ZA
dc.identifier.citationMofokeng, T. 2017. Hamiltonian cycles in maximal planar graphs and planar triangulations. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Mofokeng, Tshenolo AB - In this thesis we study planar graphs, in particular, maximal planar graphs and general planar triangulations. In Chapter 1 we present the terminology and notations that will be used throughout the thesis and review some elementary results on graphs that we shall need. In Chapter 2 we study the fundamentals of planarity, since it is the cornerstone of this thesis. We begin with the famous Euler's Formula which will be used in many of our results. Then we discuss another famous theorem in graph theory, the Four Colour Theorem. Lastly, we discuss Kuratowski's Theorem, which gives a characterization of planar graphs. In Chapter 3 we discuss general properties of a maximal planar graph, G particularly concerning connectivity. First we discuss maximal planar graphs with minimum degree i, for i = 3; 4; 5, and the subgraph induced by the vertices of G with the same degree. Finally we discuss the connectivity of G, a maximal planar graph with minimum degree i. Chapter 4 will be devoted to Hamiltonian cycles in maximal planar graphs. We discuss the existence of Hamiltonian cycles in maximal planar graphs. Whitney proved that any maximal planar graph without a separating triangle is Hamiltonian, where a separating triangle is a triangle such that its removal disconnects the graph. Chen then extended Whitney's results and allowed for one separating triangle and showed that the graph is still Hamiltonian. Helden also extended Chen's result and allowed for two separating triangles and showed that the graph is still Hamiltonian. G. Helden and O. Vieten went further and allowed for three separating triangles and showed that the graph is still Hamiltonian. In the second section we discuss the question by Hakimi and Schmeichel: what is the number of cycles of length p that a maximal planar graph on n vertices could have in terms of n? Then in the last section we discuss the question by Hakimi, Schmeichel and Thomassen: what is the minimum number of Hamiltonian cycles that a maximal planar graph on n vertices could have, in terms of n? In Chapter 5, we look at general planar triangulations. Note that every maximal planar graph on n ≥ 3 vertices is a planar triangulation. In the first section we discuss general properties of planar triangulations and then end with Hamiltonian cycles in planar triangulations. DA - 2017 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 2017 T1 - Hamiltonian cycles in maximal planar graphs and planar triangulations TI - Hamiltonian cycles in maximal planar graphs and planar triangulations UR - http://hdl.handle.net/11427/25389 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/25389
dc.identifier.vancouvercitationMofokeng T. Hamiltonian cycles in maximal planar graphs and planar triangulations. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2017 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/25389en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Mathematics and Applied Mathematicsen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherMathematicsen_ZA
dc.titleHamiltonian cycles in maximal planar graphs and planar triangulationsen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_2017_mofokeng_tshenolo.pdf
Size:
1.25 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters