Barioli, Francesco; Saleh, Ossama; Van der Merwe, Lucas
College of Arts and Sciences
University of Tennessee at Chattanooga
Place of Publication
The induced path number rho(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path. A complementary prism of a graph G that we will refer to as CP(G) is the graph formed from the disjoint union of G and G_bar and adding the edges between the corresponding vertices of G and G_bar. These new edges are called prism edges. The graph grid(n,m) is the Cartesian product of P_n with P_m. In this thesis we will give an overview of a selection of important results in determining rho(G) of various graphs, we will then provide proofs for determining the exact value of rho(CP(grid(n,m))) for specific values of n and m.
This work would not have been possible without the help and advice of many people. I would like to thank the Department of Mathematics and the Graduate School at UTC for giving me the opportunity to continue my studies. I would like to thank the Thesis committee for their input. I would also like to thank Dr. Walters for his invaluable revisions.
M. S.; A thesis submitted to the faculty of the University of Tennessee at Chattanooga in partial fulfillment of the requirements of the degree of Master of Science.
Graph theory; Directed graphs
ix, 53 leaves
Christopher, Jeffrey, "Induced path number for the complementary prism of a grid graph" (2019). Masters Theses and Doctoral Dissertations.