On Hamilton cycles in regular graphs / Nor Nadia Zainal Abidin

• Main Author: Nor Nadia, Zainal Abidin
• Format: Thesis
• Published: 2017
• Subjects: Q Science (General)
• Online Access: http://studentsrepo.um.edu.my/7254/4/nor_nadia.pdf; http://studentsrepo.um.edu.my/7254/

The purpose of this dissertation is to discuss the hamiltonicity of r-regular 3-connected planar graphs (rR3CPs) with faces of given types, in particular, r ∈ {3, 4}. In general, let Gr (k1, k2, . . . , kt) denotes the class of all rR3CPs whose faces are of only t types, namely k1-, k2-, . . . , kt-gons where ki ≥ 3, ki 6= kj ∀ i 6= j and i, j ∈ {1, 2, . . . , t}. The problem related to the hamiltonicity of 3R3CPs with only two types of faces are widely discussed and many results have been found. These results are reviewed in Chapter 2. Chapter 3 is devoted to the constructions of non-hamiltonian 3R3CPs with only three types of faces. Here, we show that G3(3, k, l) is empty if 11 ≤ k < l. We also show that for h 6= k 6= l, there exist non-hamiltonian members in (1) G3(3, k, l) for 4 ≤ k ≤ 10 and l ≥ 7; (2)(i) G3(4, k, l) for k ∈ {3, 5, 7, 9, 11} and l ≥ 8; and (k, l) ∈ {(3, 7),(6, 7),(6, 9),(6, 11)}; (2)(ii) G3(4, k, k + 5) and G3(4, k + 2, k + 5) for k ≥ 3; (3) G3(5, k, l) for k = 3 and l ≥ 7; k = 4 and l ≥ 8; and 6 ≤ k < l. Results (1), (2) and (3) are presented in Sections 3.3, 3.4 and 3.5, respectively. Chapter 4 deals with the hamiltonicity of 4R3CPs with faces of given types. We construct non-hamiltonian members of G4(3, 7) and G4(3, 8). Additionally, we show that for k 6= l and (k, l) 6∈ {(6, 9),(9, 10),(9, 11)}, there exist non-hamiltonian members in G4(3, k, l) for k ≥ 4 and l ≥ 7