The full text of this article is unavailable through your IP address: 3.23.102.79
Contents Online
Journal of Combinatorics
Volume 12 (2021)
Number 1
Zero-forcing in random regular graphs
Pages: 85 – 116
DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n1.a4
Authors
Abstract
The zero-forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero-forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero-forcing number is the size of the smallest zero-forcing set. We explore the zero-forcing number for random regular graphs, improving on bounds given by Kalinowski, Kamčev and Sudakov [15]. We also propose and analyze a degree-greedy algorithm for finding small zero-forcing sets using the differential equations method.
Keywords
zero-forcing number, random regular graphs, random graphs, DE method, expanders
Patrick Bennett was supported in part by Simons Foundation Grant #426894.
Calum MacRury and Paweł Prałat were supported in part by the Natural Sciences and Engineering Research Council.
Received 5 January 2019
Accepted 19 March 2020
Published 4 January 2021