Document Type : Research Paper

**Authors**

Shahid Bahonar University of Kerman

**Abstract**

The zero forcing number $Z(G)$ of a graph $G$ is the minimum cardinality of a set $S$ with colored (black) vertices which forces the set $V(G)$ to be colored (black) after some times. ``color change rule'': a white vertex is changed to a black vertex when it is the only white neighbor of a black vertex. In this case, we say that the black vertex forces the white vertex. We investigate here the concept of connected zero forcing set and connected zero forcing number. We discusses this subject for special graphs and some products of graphs. Also we introduce the connected propagation time. Graphs with extreme minimum connected propagation times and maximum propagation times $|G|-1$ and $|G|-2$ are characterized.

**Keywords**

**Main Subjects**

[1] AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler and S. M. Cioabă, D.

Cvetković, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha,

W. So, D. Stevanović, H. van der Holst, K. Vander Meulen and A. Wangsness), Zero forcing sets and the minimum

rank of graphs, Linear Algebra Appl., 428 (2008) 1628–1648.

Cvetković, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha,

W. So, D. Stevanović, H. van der Holst, K. Vander Meulen and A. Wangsness), Zero forcing sets and the minimum

rank of graphs, Linear Algebra Appl., 428 (2008) 1628–1648.

[2] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, H. van der Holst and B. Shader, Zero forcing parameters

and minimum rank problems, Linear Algebra Appl., 433 (2010) 401–411.

and minimum rank problems, Linear Algebra Appl., 433 (2010) 401–411.

[3] F. Barioli, S. Fallat, D. Hershkowitz, H. T. Hall, L. Hogben, H. van der Holst and B. Shader, On the minimum rank

of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra, 18 (2009) 126–145.

of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra, 18 (2009) 126–145.

[4] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche and H. van der Holst,

Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory, 72 (2013) 146–177.

Parameters related to tree-width, zero forcing, and maximum nullity of a graph, J. Graph Theory, 72 (2013) 146–177.

[5] B. Brimkov and R. Davila, Characterizations of the Connected Forcing Number of a Graph, https://arxiv.org/

pdf/1604.00740.

pdf/1604.00740.

[6] S. Butler and M. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin., 57 (2013)

65–71.

65–71.

[7] 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.

Combin. Appl., 64 (2012) 57–72.

[8] J. Ekstrand, C. Erickson, H. T. Hall, D. Hay, L. Hogben, R. Johnson, N. Kingsley, S. Osborne, T. Peters, J. Roat,

A. Ross, D. Row, N. Warnberg and M. Young, Positive semidefinite zero forcing, Linear Algebra Appl., 439 (2013)

1862–1874.

A. Ross, D. Row, N. Warnberg and M. Young, Positive semidefinite zero forcing, Linear Algebra Appl., 439 (2013)

1862–1874.

[9] S. Fallat and L. Hogben, The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra

Appl., 426 (2007) 558–582.

Appl., 426 (2007) 558–582.

[10] L. Hogben, Minimum rank problems, Linear Algebra Appl., 432 (2010) 1961–1974.

[11] L. Hogben, M. Huynh, N. Kingsley, S. Meyer, Sh. Walker and M. Young, Propagation time for zero forcing on a

graph, Discrete Appl. Math., 160 (2012) 1994–2005.

graph, Discrete Appl. Math., 160 (2012) 1994–2005.

[12] L.-H. Huang, G. J. Chang and H.-G. Yeh, On minimum rank and zero forcing sets of a graph, Linear Algebra Appl.,

432 (2010) 2961–2973.

432 (2010) 2961–2973.

[13] C. R. Johnson, R. Loewy and P. A. Smith, The graphs for which the maximum multiplicity of an eigenvalue is two,

Linear Multilinear Algebra, 57 (2009) 713–736.

Linear Multilinear Algebra, 57 (2009) 713–736.

[14] T. Peters, Semidefinite maximum nullity and zero forcing number, Electron. J. Linear Algebra, 23 (2012) 815–830.

[15] D. D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl.,

436 (2012) 4423–4432.

436 (2012) 4423–4432.

June 2020

Pages 77-88

**Receive Date:**25 January 2019**Revise Date:**18 January 2020**Accept Date:**19 January 2020**Published Online:**01 June 2020