GRAPHS WITH TOTAL FORCING NUMBER TWO, REVISITED

Document Type : Original Manuscript

Authors

Faculty of Mathematical Sciences, Shahrood University of Technology, P.O. Box: 316-3619995161, Shahrood, Iran.

Abstract

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$.

Keywords

References

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.
 
Journal of Algebraic Systems
Volume 9, Issue 1
September 2021
Pages 53-60

Files

Share

How to cite

Statistics