Date of Award

1-1-2001

Thesis Type

PhD

Document Type

Thesis

Divisions

Faculty of Science

Department

Institute of Mathematical Sciences

Institution

Universiti Malaya

Abstract

This thesis is divided into two parts, both related to hamiltonian graphs. The first part deals with 3-connected cubic bipartite planar graphs. By assuming that all 3-connected cubic bipartite planar graphs are hamiltonian, lower bounds for the number of Hamilton cycles in cubic bipartite planar graphs with given cyclic connectivity are obtained in Chapter 2. In Chapter 3, we show that Barnette's Conjecture is equivalent to the conjecture which states that for any two edges x and y on the same face of a 3-connected cubic bipartite planar hamiltonian graph, there is a Hamilton cycle passing through x and y1 and another one passing through x but avoiding y. As a byproduct, by assuming that every 3-connected cubic bipartite planar graph is hamiltonian, we characterize all those cubic bipartite planar graphs with given cyclic connectivity and whose number of Hamilton cycles is n for n = 6 and n = 12. The second part deals with the Generalized Knight's Tour Problem. We show that certain rectangular chessboards do not admit a closed (a, b)­knight's tour in Chapter 4. In Chapter 5, for all positive integers k, we obtain the values of n for which the 5k x n chessboard, except for the 5 x 18 chessboard1 admits a closed (21 3)-knight's tour.

Initial

snms

Additional Information

Thesis (PhD) -- Faculty of Science, Universiti Malaya, 2002.

Download

Share

COinS