- Title
- The path partition number of a graph
- Creator
- Jonck, Elizabeth
- Subject
- Algebra - Graphic methods., Graphic methods - Problems, exercises, etc., Graph theory., Path analysis.
- Date
- 2012-09-06
- Type
- Thesis
- Identifier
- uj:9705
- Identifier
- http://hdl.handle.net/10210/7118
- Description
- 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.
- Contributor
- Prof. I. Broere
- Full Text

- Hits: 385
- Visitors: 439
- Downloads: 145

Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|

View Details Download | CONTENT1 | PDF Document | 1 MB | Adobe Acrobat PDF | View Details Download | ||

View Details Download | MODS | MODS Metadata | 3 KB | XML Document | View Details Download |