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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:9705 |
| Date | 06 September 2012 |
| Creators | Jonck, Elizabeth |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds