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

Deepak Bal (Department of Mathematical Sciences, Montclair State University, Montclair, New Jersey, U.S.A.)

Patrick Bennett (Department of Mathematics, Western Michigan University, Kalamazoo, Mich., U.S.A.)

Sean English (Department of Mathematics, University of Illinois, Urbana-Champaign, Il., U.S.A.)

Calum Macrury (Department of Computer Science, University of Toronto, Ontario, Canada)

Paweł Prałat (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

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

Full Text (PDF format)

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