Variations on Graph Products and Vertex Partitions

In this thesis we investigate two graph products called double vertex graphs and complete double vertex graphs, and two vertex partitions called dominator partitions and rankings. We introduce a new graph product called the complete double vertex graph and study its properties. The complete double vertex graph is a natural extension of the Cartesian product and a generalization of the double vertex graph. We establish many properties of complete double vertex graphs, including results involving the chromatic number of a complete double vertex graph and the characterization of planar complete double vertex graphs. We also investigate the important problem of reconstructing the factors of double vertex graphs and complete double vertex graphs. We reconstruct G from double vertex graphs and complete double vertex graphs for different classes of graphs, including cubic graphs. Next, we look at the properties of dominator partitions of graphs. We characterize minimal dominator partitions of a graph G. This helps us to study the properties of the upper dominator partition number and establish bounds on the upper dominator partition number of different families of graphs, including trees. We also calculate the upper dominator partition number of certain classes of graphs, including paths and cycles, which is surprisingly difficult to calculate. Properties of rankings are studied in this thesis as well. We establish more properties of minimal rankings, including results related to permuting the labels of certain minimal rankings of a graph G. In addition, we investigate rankings of the Cartesian product of two complete graphs, also known as the rook's graph. We establish bounds on the rank number of a rook's graph and calculate its arank number using multiple results we obtain on minimal rankings of a rook's graph.