Extremal problems about bootstrap percolation on graphs

Loading...
Thumbnail Image
Date
2020-12
Authors
Zhao, Ruoxin
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

Bootstrap percolation is a dynamic process on configurations of two possible states of vertices in a graph. For a given graph and a fixed non-negative integer threshold, some vertices are initially "activated" whilst others are "inactivated". At each step, every inactivated vertex will become activated if the number of their activated neighbours is at least the threshold. If all the vertices are eventually activated, then say the set of initially activated vertices percolates. In this thesis, I focus on percolating sets containing as few vertices as possible - minimal and minimum percolating sets. Specifically, I survey exact and approximate cardinalities of minimal/minimum percolating sets of some classes of graphs, and obtain several new bounds and constructions for them. The main tools used in the thesis are structural properties and invariants of graphs. Throughout the thesis, I also present the major outstanding new problems in this area.

Description
Keywords
Boothstrap percolation, Minimal percolating sets, Minimum percolating set, Regular graphs, Grid graphs, Trees
Citation