In this dissertation we study the Hamiltonicity and the uniform-Hamiltonicity of subset graphs, subspace graphs, and their associated bipartite graphs. In 1995 paper "The Subset-Subspace Analogy," Kung states the subspace version of a conjecture. The study of this problem led to a more general class of graphs. Inspired by Clark and Ismail's work in the 1996 paper "Binomial and Q-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and their Q-Analogues," we defined subset graphs, subspace graphs, and their associated bipartite graphs. The main emphasis of this dissertation is to describe those graphs and study their Hamiltonicity. The results on subset graphs are presented in Chapter 3, on subset bipartite graphs in Chapter 4, and on subspace graphs and subspace bipartite graphs in Chapter 5. We conclude the dissertation by suggesting some generalizations of our results concerning the panciclicity of the graphs.

A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. / Mathematical Sciences / PHD (MATHEMATICS)

A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. / Mathematical Sciences / PHD (MATHEMATICS)

No description available.