Abstract
Ph.D.
The induced path number p(G) of a graph G is defined as the minimum number of subsets
into which the vertex set V(G) of G can be partitioned such that each subset induces a path.
In this thesis we determine the induced path number of a complete £-partite graph.
We investigate the induced path number of products of complete graphs, of the complement
of such products and of products of cycles.
For a graph G, the linear vertex arboricity lva(G) is defined as the minimum number of
subsets into which the vertex set of C can be partitioned so that each subset induces a linear
forest. Since each path is a linear forest, Iva(G) p(G) for each graph C. A graph G is said
to be uniquely rn-li near- forest- partition able if lva(C) = in and there is only one partition
of V(G) into m subsets so that each subset induces a linear forest. Furthermore, a graph
C is defined to be nz- Iva- saturated if Iva(G) < in and lva(C + e) > iii for each e E
We construct graphs that are uniquely n2-linear-forest-partitionable and in-lva-saturated.
We characterize those graphs that are uniquely m-linear-forest-partitionable and rn-lvasaturated.
We also characterize the orders of uniquely in- path- partitionable disconnected,
connected and rn-p-saturated graphs.
We look at the influence of the addition or deletion of a vertex or an edge on the path partition
number. If C is a graph such that p(G) = k and p(G - v) = k - 1 for every v E V(G),
then we say that C is k-minus-critical. We prove that if C is a connected graph consisting
of cyclic blocks Bi with p(B1 ) = b, for i = 1,2, ... ,n where ii > 2 and k bi - n+ 1,
then C is k- minus- critical if and only if each of the blocks B1 is a bj- minus- critical graph.