Back to Search
Start Over
On the zero blocking number of rectangular, cylindrical, and Möbius grids.
- Source :
-
Discrete Applied Mathematics . Aug2020, Vol. 282, p35-47. 13p. - Publication Year :
- 2020
-
Abstract
- In a zero forcing process , an initial vertex coloring of a graph is updated iteratively according to the following conversion rule: an uncolored vertex becomes colored if it is the only uncolored neighbor of some colored vertex. In this process, a zero forcing set is an initial set of colored vertices such that all the remaining vertices will ultimately change from uncolored to colored, and the zero forcing number is the minimum cardinality of a zero forcing set. We investigate two related concepts: a zero blocking set is the complement of a set which is not a zero forcing set, and the zero blocking number is the minimum cardinality of a zero blocking set. We provide upper and lower bounds for the zero blocking number of rectangular grids and discuss conditions under which these bounds coincide. We go on to use the same machinery to provide similar results for certain cylindrical and Möbius grids. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH coloring
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 282
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 143599059
- Full Text :
- https://doi.org/10.1016/j.dam.2019.11.015