Edge Forcing in Butterfly Networks

• Autorzy: Jessy Sujana G , Rajasingh Indra , Rajalaxmi T.M. , Rajan R. Sundara

Identyfikatory

DOI

10.3233/FI-2021-2074

• Języki publikacji: EN

Abstrakty

EN

A zero forcing set is a set S of vertices of a graph G, called forced vertices of G, which are able to force the entire graph by applying the following process iteratively: At any particular instance of time, if any forced vertex has a unique unforced neighbor, it forces that neighbor. In this paper, we introduce a variant of zero forcing set that induces independent edges and name it as edge-forcing set. The minimum cardinality of an edge-forcing set is called the edge-forcing number. We prove that the edge-forcing problem of determining the edge-forcing number is NP-complete. Further, we study the edge-forcing number of butterfly networks. We obtain a lower bound on the edge-forcing number of butterfly networks and prove that this bound is tight for butterfly networks of dimensions 2, 3, 4 and 5 and obtain an upper bound for the higher dimensions.

Słowa kluczowe

EN

Zero forcing set; forced vertex; independent set; edge-forcing set; butterfly networks

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 3
• Strony: 285--299
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Jessy Sujana G

• Department of Computer Science and Engineering Sri Sivasubramaniya Nadar College of Engineering Chennai, 603 110, India

autor

Rajasingh Indra

• School of Advanced Sciences Vellore Institute of Technology Chennai, 600 127, India

autor

Rajalaxmi T.M.

• Department of Mathematics Sri Sivasubramaniya Nadar College of Engineering Chennai, 603 110, India

autor

Rajan R. Sundara

• Department of Mathematics Hindustan Institute of Technology and Science Chennai, 603 103, India

Bibliografia

• [1] Benson KF, Ferrero D, Flagg M, Furst V, Hogben L, Vasilevska V, Wissman B. Power domination and zero forcing. arXiv: 1510.02421, 2015.
• [2] Ferrero D, Grigorious C, Kalinowski T, Ryan J, Stephen S. Minimum rank and zero forcing number for butterfly networks. Journal of Combinatorial Optimization, 2019. 37:970-988. doi:10.1007/s10878-018-0335-1.
• [3] Group AMRSGW. Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, 2008. 428:1628-1648. doi:10.1016/j.laa.2007.10.009.
• [4] Burgarth D, Giovannetti V. Full control by locally induced relaxation. Physical Review Letters, 2007. 99(10):100501. doi:10.1103/PhysRevLett.99.100501.
• [5] Burgarth D, Maruyama K. Indirect Hamiltonian identification through a small gateway. New Journal of Physics, 2009. 11:103019. doi:10.1088/1367-2630/11/10/103019.
• [6] Fallat S, Meagher K, Yang B. On the complexity of the positive semidefinite zero forcing number. Linear Algebra and its Applications, 2016. 491:101-122. doi:10.1016/j.laa.2015.03.011.
• [7] Rashidi S, Poursalavati NS, Tavakkoli M. Computing the zero forcing number for generalized Petersen graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 2019. 7(2):183-193. doi:10.13069/jacodesmath.729465.
• [8] Row DD. Zero forcing number, path cover number, and maximum nullity of cacti. Involve: A Journal of Mathematics, 2011. 4:277-291. doi:10.2140/involve.2011.4.277.
• [9] Davila R, Kenter F. Bounds for the Zero Forcing Number of Graphs with Large Girth. Theory and Applications of Graphs, 2015. 2. doi:10.20429/tag.2015.020201.
• [10] Kalinowski T, Kamcev N, Sudakov B. The Zero Forcing Number of Graphs. SIAM Journal of Discrete Mathematics, 2019. 33:95-115. doi:10.1137/17M1133051.
• [11] Anitha J. Zero Forcing in Snake Graph. International Journal of Recent Technology and Engineering, 2019. 7:133-136. ISSN:2277-3878.
• [12] Eroh L, Kang CX, Yi E. A comparison between the Metric Dimension and Zero Forcing Number of Line Graphs. arXiv:1207.6127v1 [math.CO] 25 Jul 2012.
• [13] Hayat S, Siddiqui HMA, Imran M, Ikhlaq HM. On the zero forcing number and propagation time of oriented graphs. AIMS Press, 2021. 6(2):1833-1850. doi: 10.3934/math.2021111.
• [14] Vatandoost E, Ramezani F, Alikhan S. On the zero forcing number of generalized Sierpinski graphs. Transactions on Combinatorics, 2019. 8:41-50.
• [15] Stephen S. Zero Forcing and Power Domination in Graphs. PhD thesis, The University of Newcastle, Australia, 2017.
• [16] Hogben L, Huynh M, Kingsley N, Meyer S, Walker S, Young M. Propagation time for zero forcing on a graph. Discrete Applied Mathematics, 2012. 160(13-14):1994–2005. doi:10.1016/j.dam.2012.04.003.
• [17] Davila R, Henning MA. On the total forcing number of a graph. Discrete Applied Mathematics, 2019. 257:115-127. doi:10.1016/j.dam.2018.09.001.
• [18] Haynes TW, Hedetniemi SM, Hedetneimi ST, Henning MA. Domination in graphs applied to elec-tric power networks. SIAM Journal on Discrete Mathematics, 2002. 15(4):519-529. doi:10.1137/S0895480100375831.
• [19] Davila R, Henning MA, Magnant C, Pepper R. Bounds on the Connected Forcing Number of a Graph. Graphs and Combinatorics, 2018. 34(6):11591174. doi:10.1007/s00373-018-1957-x.
• [20] Ferrero D, Varghese S, Vijayakumar A. Power domination in honeycomb networks. Journal of Discrete Mathematical Sciences and Cryptography, 2011. 14(6):521-529. doi:10.1080/09720529.2011.10698353.
• [21] Amos D, Caro Y, Randy Davila RP. Upper bounds on the k-forcing number of a graph. arXiv:1401.6206 [math.CO].
• [22] Davila R, Henning MA. On the Total Forcing Number of a Graph. arXiv:1702.06035v3 [math.CO] 27 Feb 2017.
• [23] Konstantinidou S. The selective extra stage butterfly. IEEE Transactions on Very Large Scale Integration Systems, 1993. 1:167-171. doi:10.1109/92.238419.
• [24] Shrinivas SG, Vetrivel S, Elango NM. Applications of graph theory in computer science-An overview. International Journal of Engineering Science and Technology, 2010. 2:4610-4621. ID:15834618.
• [25] Manuel PD, Rajan B, Rajasingh I, Beulah PV. Improved bounds on the crossing number of butterfly network. Journal of Discrete Mathematics and Theoretical Computer Science, 2013. 15(2):87-94. doi:10.46298/dmtcs.611.
• [26] Rajasingh I, Rajan B, Arockiamary ST. Irregular total labeling of butterfly and Benes networks. Irregular total labeling of butterfly and Benes networks, 2011. 253:284-293. doi:10.1007/978-3-642-25462-8 25.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)