Connected zero forcing sets and connected propagation time of graphs

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

References

[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.
[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.
[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.
[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.
[5] B. Brimkov and R. Davila, Characterizations of the Connected Forcing Number of a Graph, https://arxiv.org/
pdf/1604.00740.
[6] S. Butler and M. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin., 57 (2013)
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.
[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.
[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.
[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.
[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.
[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.
[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.

Files

History

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

Share

How to cite

Statistics