تعداد نشریات | 43 |
تعداد شمارهها | 1,659 |
تعداد مقالات | 13,577 |
تعداد مشاهده مقاله | 31,261,744 |
تعداد دریافت فایل اصل مقاله | 12,312,365 |
Connected zero forcing sets and connected propagation time of graphs | ||
Transactions on Combinatorics | ||
مقاله 23، دوره 9، شماره 2، شهریور 2020، صفحه 77-88 اصل مقاله (269.26 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2020.115286.1617 | ||
نویسندگان | ||
Maryam Khosravi؛ Saeedeh Rashidi* ؛ Alemeh Sheikhhosseini | ||
Shahid Bahonar University of Kerman | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
zero forcing number؛ connected zero forcing number؛ propagation time | ||
مراجع | ||
[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. | ||
آمار تعداد مشاهده مقاله: 293 تعداد دریافت فایل اصل مقاله: 217 |