Zero forcing number for Cartesian product of some graphs

Document Type : Original paper

Authors

Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran

Abstract

The zero forcing number of a graph $G$, denoted $Z(G)$, is a graph parameter  which is based on a color change rule that describes how to color the vertices. Zero forcing is useful in several branches of science such as electrical engineering, computational complexity and quantum control.  In this paper, we investigate the zero forcing number for Cartesian products of some graphs. The main contribution of this paper is to introduce a new presentation of the Cartesian product of two complete bipartite graphs and to obtain the zero forcing number of these graphs.  We also introduce a purely graph theoretical method to prove $Z(K_n \Box K_m)=mn-m-n+2$.

Keywords

Main Subjects

References

[1] K. Benson, D. Ferrero, M. Flagg, L. Hogben, V. Furst, V. Vasilevska, and B. Wissman, Zero forcing and power domination for graph products, Australas. J. Combin. 70, no. 2. , 221–235.
[2] B. Brimkov and I.V. Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math. 229 (2017), 31–45.
https://doi.org/10.1016/j.dam.2017.05.016
[3] D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett. 99 (2007), no. 10, Article ID: 100501.
https://doi.org/10.1103/PhysRevLett.99.100501
[4] K.B. Chilakamarri, N. Dean, C.X. Kang, and E. Yi, Iteration index of a zero forcing set in a graph, Bull. Inst. Combin. Appl. 64 (2012), 57–72.
[5] AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648.
https://doi.org/10.1016/j.laa.2007.10.009
[6] L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. Walker, and M. Young, Propagation time for zero forcing on a graph, Discrete Appl. Math. 160 (2012), no. 13-14, 1994–2005.
https://doi.org/10.1016/j.dam.2012.04.003
[7] D.D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl. 436 (2012), no. 12, 4423–4432.
https://doi.org/10.1016/j.laa.2011.05.012
[8] S. Severini, Nondiscriminatory propagation on trees, J. Phys. A 41 (2008), no. 48, Article ID: 482002.
https://doi.org/10.1088/1751-8113/41/48/482002
[9] F.A. Taklimi, S. Fallat, and K. Meagher, On the relationships between zero forcing numbers and certain graph coverings, Special Matrices 2 (2014), no. 1. 30-45.
https://doi.org/10.2478/spma-2014-0004
[10] D.B. West, Introduction to Graph Theory, vol. 2, Prentice hall Upper SaddleRiver, USA, 2001.
[11] B. Yang, Fast–mixed searching and related problems on graphs, Theoret. Comput. Sci. 507 (2013), 100–113.
https://doi.org/10.1016/j.tcs.2013.04.015
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 24 May 2023

Files

Share

How to cite

Statistics