On the Zero Forcing Number of Complementary Prism Graphs

Document Type : Original paper

Authors

1 Department of Mathematics, CHRIST(Deemed to be University) Bangalore India

2 Department of Mathematics CHRIST(Deemed to be University) Bangalore India

Abstract

The zero forcing number of a graph is the minimum cardinality among all the zero forcing sets of a graph $G$.  The aim of this article is to compute the zero forcing number of complementary prism graphs.  Some bounds on the zero forcing number of complementary prism graphs are presented. The remainder of this article discusses the following result.  Let $G$ and $\overline{G }$ be connected graphs. Then $Z(G\overline{G})\leq n-1$ if and only if  there exists two vertices $v_i,v_j \in V(G)$ and $i\neq j$ such that, either $N(v_i) \subseteq N(v_j)$ or $N[v_i] \subseteq N[v_j]$ in $G$.

Keywords

Main Subjects

References

[1] D. Burgarth, S. Bose, C. Bruder, and V. Giovannetti, Local controllability ofquantum networks, Physical Review A 79 (2009), no. 6, Article ID: 060305.
https://doi.org/10.1103/PhysRevA.79.060305
[2] D. Burgarth and V. Giovannetti, Full control by locally induced relaxation, Physical Review Lett. 99 (2007), no. 10, Article ID: 100501.
https://doi.org/10.1103/PhysRevLett.99.100501
[3] D. Burgarth, V. Giovannetti, L. Hogben, S. Severini, and M. Young, Logic circuits from zero forcing, Natural computing 14 (2015), no. 3, 485–490.
https://doi.org/10.1007/s11047-014-9438-5
[4] S. Butler and M. Young, Throttling zero forcing propagation speed on graphs, Australas. J. Combin. 57 (2013), 65–71.
[5] B. Chaluvaraju and V. Chaitra, Roman domination in complementary prism graphs, Math. Combin. 2 (2012), 24–31.
[6] L. Eroh, C.X. Kang, and E. Yi, On zero forcing number of graphs and their complements, Discrete Math. Algorithms Appl. 7 (2015), no. 1, Article ID: 1550002.
https://doi.org/10.1142/S1793830915500020
[7] M. Gentner, L.D. Penso, D. Rautenbach, and U.S. Souza, Extremal values and bounds for the zero forcing number, Discrete Appl. Math. 214 (2016), 196–200.
https://doi.org/10.1016/j.dam.2016.06.004
[8] M. Gentner and D. Rautenbach, Some bounds on the zero forcing number of a graph, Discrete Appl. Math. 236 (2018), 203–213.
https://doi.org/10.1016/j.dam.2017.11.015
[9] T.W. Haynes, M.A. Henning, P.J. Slater, and L.C. van der Merwe, The complementary product of two graphs, Bull. Ins. Combin. Appl. 51 (2007), 21–30.
[10] T. Kalinowski, N. Kamčev, and B. Sudakov, The zero forcing number of graphs, SIAM J. Discrete Math. 33 (2019), no. 1, 95–115.
https://doi.org/10.1137/17M1133051
[11] L. Lu, B. Wu, and Z. Tang, Proof of a conjecture on the zero forcing number of a graph, Discrete Appl. Math. 213 (2016), 233–237.
https://doi.org/10.1016/j.dam.2016.05.009
[12] Z. Montazeri and N. Soltankhah, Zero forcing number for Cartesian product of some graphs, Commun. Comb. Optim., In press
https://doi.org/10.22049/cco.2023.28177.1471
[13] D.B. West, Introduction to graph theory, vol. 2, Prentice hall Upper Saddle River, 2001.
[14] AIM Minimum Rank-Special Graphs Work Group Work, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648.
https://doi.org/10.1016/j.laa.2007.10.009
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 December 2023

Files

Share

How to cite

Statistics