Please be patient while the object screen loads.

Sign In

GlobalView

Add to Quick Collection

Jonck, Elizabeth. The path partition number of a graph. 2012-09-06.

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

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

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

Please use this identifier to cite or link to this item: http://hdl.handle.net/10210/7118

- Title
- The path partition number of a graph
- Creator
- Jonck, Elizabeth
- Contributor
- Prof. I. Broere
- Subject
- Algebra - Graphic methods.
- Subject
- Graphic methods - Problems, exercises, etc.
- Subject
- Graph theory.
- Subject
- Path analysis.
- Date
- 2012-09-06
- Description
- Ph.D.
- Description
- 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.

- Relationships
- Show Relationship Browser for this Object
- collection(s)
- 22
- collection(s)
- ETDs
- Identifier
- uj:9705
- Identifier
- http://hdl.handle.net/10210/7118
- Type
- Thesis
- Full Text

180 Visitors
134 Hits
59 Downloads

Disclaimer |
Privacy |
Copyright |
Contact |
Back To Top