Committee Chair

Walters, Terry

Committee Member

Barioli, Francesco; Saleh, Ossama; Van der Merwe, Lucas

Department

Dept. of Mathematics

College

College of Arts and Sciences

Publisher

University of Tennessee at Chattanooga

Place of Publication

Chattanooga (Tenn.)

Abstract

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.

Acknowledgments

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.

Degree

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.

Date

5-2019

Subject

Graph theory; Directed graphs

Keyword

Induced path number; Complementary prisms; Graph; Grid(n,m)

Document Type

Masters theses

Extent

ix, 53 leaves

Language

English

Rights

Under copyright.

License

http://creativecommons.org/licenses/by/3.0/

Share

COinS