Title
Properties of a q-analogue of zero forcing
Department/School
Mathematics
Date
1-1-2020
Document Type
Article
Keywords
zero forcing, propagation, trees, combs
DOI
https://doi.org/10.1007/s00373-020-02208-2
Abstract
Zero forcing is a combinatorial game played on a graph where the goal is to start with all vertices unfilled and to change them to filled at minimal cost. In the original variation of the game there were two options. Namely, to fill any one single vertex at the cost of a single token; or if any currently filled vertex has a unique non-filled neighbor, then the neighbor is filled for free. This paper investigates a q-analogue of zero forcing which introduces a third option involving an oracle. Basic properties of this game are established including determining all graphs which have minimal cost 1 or 2 for all possible q, and finding the zero forcing number for all trees when q=1.
Published in
Graphs and Combinatorics
Citation/Other Information
Butler, S., Erickson, C., Fallat, S., Hall, H. T., Kroschel, B. K., Lin, J. C.-H., Shader, B., Warnberg, N., & Yang, B. (2020). Properties of a q-Analogue of Zero Forcing. Graphs and Combinatorics, 36(5), 1401–1419. https://doi.org/10.1007/s00373-020-02208-2