University of Victoria (Canada)
Irreversible k-threshold conversion processes on graphs
Abstract
dc:description.abstractGiven a graph G and an initial colouring of its vertices with two colours, say black and white, an irreversible k-threshold conversion process on G is an iterative process in which a white vertex becomes permanently coloured black at time t if at least k of its neighbours are coloured black at time t-1. A set S of vertices is an irreversible k-threshold conversion set (k-conversion set) of G if the initial colouring in which the vertices of S are black and the others are white results in the whole vertex set becoming black eventually. In the case where G is (k+1)-regular, it can be shown that the k-conversion sets coincide with the so-called feedback vertex sets, or decycling sets. In this dissertation we study the size and structure of minimum k-conversion sets in several classes of graphs. We examine conditions that lead to equality and inequality in existing bounds on the minimum size of a k-conversion set of G, for k- and (k+1)-regular graphs G. Furthermore, we derive new sharp lower bounds on this number for regular graphs of degree ranging from k+1 to 2k-1 and for graphs of maximum degree k+1. We determine exact values of the minimum size of a k-conversion set for certain classes of trees. We show that every (k+1)-regular graph has a minimum k-conversion set that avoids certain structures in its induced subgraph. These results lead to new proofs of several known results on colourings and forest partitions of (k+1)-regular graphs and graphs of maximum degree k+1.
Degree
thesis:*- Level thesis:degree_level
- Doctor of Philosophy Ph.D.
- Department thesis:degree_department
- Department of Mathematics and Statistics
- Year dc:date.issued
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wodlinger, Jane
- Advisor dc:contributor.supervisor
-
- Mynhardt, C.M.
Subjects
dc:subject × 10Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/9282