Induced path number for the complementary prism of a grid graph

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.

Grantor dc:publisher

University of Tennessee at Chattanooga

Author dc:creator

• Christopher, Jeffrey

Contributors dc:contributor

• Walters, Terry
• Barioli, Francesco; Saleh, Ossama; Van der Merwe, Lucas
• College of Arts and Sciences

• Graph theory
• Directed graphs

Licence

• https://rightsstatements.org/page/InC/1.0/?language=en

Language dc:language

English, eng

Repository record dc:identifier

https://scholar.utc.edu/theses/594

OAI identifier oai:identifier

oai:scholar.utc.edu:theses-1741