GRAPHS WITH TOTAL FORCING NUMBER TWO, REVISITED | ||
| Journal of Algebraic Systems | ||
| دوره 9، شماره 1، آذر 2021، صفحه 53-60 اصل مقاله (135.38 K) | ||
| نوع مقاله: Original Manuscript | ||
| شناسه دیجیتال (DOI): 10.22044/jas.2020.9229.1451 | ||
| نویسندگان | ||
| M. Alishahi* ؛ E. Rezaei-Sani | ||
| Faculty of Mathematical Sciences, Shahrood University of Technology, P.O. Box: 316-3619995161, Shahrood, Iran. | ||
| چکیده | ||
| A subset of the vertex set of a graph $G$ is called a zero forcing set if by considering them colored and, as far as possible, a colored vertex with exactly one non-colored neighbor forces its non-colored neighbor to get colored, then the whole vertices of $G$ become colored. The total forcing number of a graph $G$, denoted by $F_t(G)$, is the cardinality of a smallest zero forcing set of $G$ which induces a subgraph with no isolated vertex. The connected forcing number, denoted by $F_c(G)$, is the cardinality of a smallest zero forcing set of $G$ which induces a connected subgraph. In this paper, we first characterize the graphs with $F_t(G)=2$ and, as a corollary, we characterize the graphs with $F_c(G)=2$. | ||
| کلیدواژهها | ||
| Zero forcing set؛ Total forcing number؛ Connected forcing number | ||
| مراجع | ||
|
1. A. Aazami, Hardness results and approximation algorithms for some problems on graphs, PhD thesis, University of Waterloo, 2008.
2. F. Barioli, W. Barrett, S. M. 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(2) (2013), 146–177. 3. B. Brimkov and R. Davila, Characterizations of the connected forcing number of a graph, arXiv preprint arXiv:1604.00740, (2016). 4. B. Brimkov, C. C. Fast, and I.V. Hicks, Graphs with extremal connected forcing numbers, arXiv preprint arXiv:1701.08500, (2017). 5. B. Brimkov and I.V Hicks, Complexity and computation of connected zero forcing, Discrete Appl. Math., 229 (2017), 31–45. 6. D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Phys. Rev. Lett., 99(10) (2017), 100501. 7. D. Burgarth, V. Giovannetti, L. Hogben, S. Severini, and M. Young, Logic circuits from zero forcing, Nat. Comput., 14(3) (2015), 485–490. 8. R. Davila and M. Henning, Total forcing sets and zero forcing sets in trees, Discuss. Math. Graph Theory, 40(3) (2020), 733–754. 9. R. Davila and M. A. Henning, On the total forcing number of a graph, Discrete Appl. Math., 257 (2019),115–127. 10. R. Davila, M. A. Henning, C. Magnant, and R. Pepper, Bounds on the connected forcing number of a graph, Graphs Combin., 34(6) (2018), 1159–1174. 11. R. Davila, Bounding the forcing number of a graph, PhD thesis, Rice University, (2015). 12. T. W. Haynes, S.M Hedetniemi, S.T Hedetniemi, and M.A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15(4) (2002), 519–529. 13. D. D. Row, A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra Appl., 436(12) (2012), 4423–4432. 14. M. M. Syslo, Characterizations of outerplanar graphs, Discrete Math., 26(1) (1979), 47–53. 15. Work, A. M. R. S. G., Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428(7) (2008), 1628–1648. | ||
|
آمار تعداد مشاهده مقاله: 453 تعداد دریافت فایل اصل مقاله: 431 |
||