Minimum Conditions for Bootstrap Percolation on the Cubic Graph
Date
2020-05
Authors
Schlortt, Casey Quinn
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Bootstrap percolation is an iterative process on the vertices of a graph. Initially, a proper, non-empty set of vertices is infected, and all other vertices are uninfected. At each iteration, every uninfected vertex with a certain number of infected neighbors becomes infected, and all infected vertices remain so permanently. At the end of the process, if all vertices are infected, percolation occurs. In this case, the initial set of infected vertices percolates the graph. Necessary and sufficient conditions for the minimum size of a percolating set and the minimum number of rounds to achieve percolation on a cubic graph of order 2n are presented, for any integer n, 2n ≥ 4.
Description
Keywords
bootstrap percolation, cubic graphs, 3-regular graphs, iterative process, 2-neighbor bootstrap percolation, majority bootstrap percolation, minimum percolating set cardinality, minimum number of rounds, Honors College
Citation
Schlortt, C. Q. (2020). Minimum conditions for bootstrap percolation on the cubic graph (Unpublished thesis). Texas State University, San Marcos, Texas.