Properties of a q -Analogue of Zero Forcing
- PDF / 473,559 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 64 Downloads / 171 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Properties of a q-Analogue of Zero Forcing Steve Butler1 • Craig Erickson2 • Shaun Fallat3 • H. Tracy Hall4 • Brenda Kroschel5 • Jephian C.-H. Lin6 • Bryan Shader7 • Nathan Warnberg8 Boting Yang9
•
Received: 4 March 2019 / Revised: 23 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
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. Keywords Zero forcing Propagation Trees Combs
Mathematics Subject Classification 05C85 68R10
1 Introduction The zero forcing game is a combinatorial game played on a graph. The game involves filling in the vertices of a graph by certain legal moves, the most important of which is the following filling rule (sometimes known as the forcing rule or coloring rule): If a filled vertex has a unique unfilled neighbor (and any number of filled neighbors), then the unfilled neighbor becomes filled. The game is summarized as follows. The Zero Forcing Game (or Z-Game)—All the vertices of the graph G are initially unfilled and there is one player who has tokens. The player will & Jephian C.-H. Lin [email protected] Extended author information available on the last page of the article
123
Graphs and Combinatorics
repeatedly apply one of the following two operations until all vertices are filled: 1. For one token, any vertex can be changed from unfilled to filled. 2. At no cost, the player can apply the filling rule. The Z-Game number of a graph, denoted Z(G), is the minimum number of tokens needed to guarantee that all vertices can be filled (this is sometimes referred to as the ‘‘zero forcing number’’ or ‘‘fast-mixed search number’’), and this parameter has also been developed independently for other purposes (see [5] and references contained therein). Zero forcing was originally developed in the combinatorial matrix theory community to provide a combinatorial bound for the minimum rank of a symmetric matrix A associated with a graph [1]. In fact, the filling rule above corresponds precisely to when a collection of zero coordinates in a null vector of such a matrix A, associated to a graph G, necessarily implies that this null vector must have been the zero vector. This basic correspondence leads to the following important result from [1]. Theorem 1 ( [1]) If A is a real-symmetric matrix with nonzero off-diagonal entries corresponding to the edges of G, then nullityðAÞ ZðGÞ
Data Loading...
