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.

No description available.

This dissertation has two principal components: the dimension of posets with planar cover graphs, and the cartesian product of posets whose cover graphs have hamiltonian cycles that parse into symmetric chains. Posets of height two can have arbitrarily large dimension. In 1981, Kelly provided an infinite sequence of planar posets that shows that the dimension of planar posets can also be arbitrarily large. However, the height of the posets in this sequence increases with the dimension. In 2009, Felsner, Li, and Trotter conjectured that for each integer h at least 2, there exists a least positive integer c(h) so that if P is a poset with a planar cover graph (the class of posets with planar cover graphs includes the class of planar posets) and the height of P is h, then the dimension of P is at most c(h). In the first principal component of this dissertation we prove this conjecture. We also give the best known lower bound for c(h), noting that this lower bound is far from the upper bound. In the second principal component, we consider posets with the Hamiltonian Cycle--Symmetric Chain Partition (HC-SCP) property. A poset of width w has this property if its cover graph has a hamiltonian cycle which parses into w symmetric chains. This definition is motivated by a proof of Sperner's theorem that uses symmetric chains, and was intended as a possible method of attack on the Middle Two Levels Conjecture. We show that the subset lattices have the HC-SCP property by showing that the class of posets with the strong HC-SCP property, a slight strengthening of the HC-SCP property, is closed under cartesian product with a two-element chain. Furthermore, we show that the cartesian product of any two posets from this strong class has the (weak) HC-SCP property.

No description available.

Le cube de Fibonacci est un sous-graphe isométrique de l'hyper- cube ayant un nombre de Fibonacci de sommets. Le cube de Fibonacci a été initialement introduit par W-J. Hsu comme un réseau d'interconnexion et, comme l'hypercube, il a des propriétés topologiques très attractives, mais avec une croissance plus modérée. Parmi ces propriétés, nous discutons de l'hamiltonicité dans le cube de Fibonacci et aussi dans le cube de Lucas qui est obtenu à partir du cube de Fibonacci en supprimant toutes les chaînes qui commencent et nissent avec 1. Nous trouvons également le nombre de som- mets des cubes de Fibonacci et Lucas ayant une certaine excentricité. En n, nous présentons une étude de deux cubes du point de vue de la domination et du 2-packing. / The Fibonacci cube is an isometric subgraph of the hypercube having a Fibonacci number of vertices. The Fibonacci cube was originally proposed by W-J. Hsu as an interconnection network and like the hypercube it has very attractive topological properties but with a more moderated growth. Among these properties, we discuss the hamiltonicity in the Fibonacci cube and also in the Lucas cube which is obtained by removing all the strings that begin and end with 1 from the Fibonacci cube. We give also the eccentricity sequences of the Fibonacci and the Lucas cubes. Finally, we present a study of both cubes from the domination and the 2-packing points of view.

No description available.