Back to search

University of Victoria (Canada)

Irreversible k-threshold conversion processes on graphs

Abstract

dc:description.abstract

Given 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 × 10

Rights

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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wodlinger, Jane. Irreversible k-threshold conversion processes on graphs. Doctor of Philosophy Ph.D. thesis, 2018. http://hdl.handle.net/1828/9282