Security in Some Interconnection Networks

Abstract

Consider a graph and imagine a set of patrolling security guards deployed for surveillance a guard stationed at a vertex can watch all neighbouring vertices. This study seek to minimize the number of guards; and the problem of finding a minimum dominating set is to select the least number of vertices where it is sufficient to station guards so that the entire graph may be watched. The above basic version of Dominating Set seeks a static protection strategy where the guards are immobile. In 2005, E. J. Cockayne introduced a better protection model called Secure Domination, in which the guards are mobile. A Secure Dominating Set provides a set of guards that monitor all the locations(vertices) with the guards capable of moving to neighbouring locations without compromising the protection of the graph. The Secure Domination Number is defined as the least number of guards that can be deployed, satisfying the above condition. The concept is not only restricted to the protection of vertices but also extended to edges. In 2016, V. R. Kulli introduced the concept of Secure Edge Domination. The proposed work is motivated by network security considerations and focuses on the protection strategies: Secure Domination and Secure Edge Domination applied to some special types of interconnection networks: Mycielski graphs, generalized Mycielskian, and wrapped butterfly network. Both the static and dynamic protection strategies are analysed in these networks. A detailed survey of literature related to Secure Domination and Secure Edge Domination is presented and all the properties and detailed descriptions of networks selected for analysis are presented. Analysis initially done in Secure Domination and Secure Edge Domination for general graphs and the known results and algorithmic complexities related to it are reviewed. Further, a graph modelling is done based on the CCTV surveillance system and propose a simple heuristic algorithm to find the Secure Dominating Set of the system, employing additional features to selected cameras to ensure the surveillance of all locations monitored by the particular system. The Mycielski graph, generalized Mycielskian, and wrapped butterfly networks are massive structures used for parallel computer architectures. The study investigate them thoroughly with a view to solving graph domination problems on such structures. Both Secure Domination and Secure Edge Domination are NP-complete problems; thus, no efficient algorithm might exist that can compute the exact number of required guards. However, it will be still be useful to find the lower and upper bounds within which the exact value might lie. Exact values for some classes of graphs applied to the first two networks have been determined along with tight bounds for the minimum number of guards. Also, propose an approximation algorithms to find Domination Number of generalized Mycielskian of general graphs and obtained Secure Edge Dominating Set of Mycielski of trees through a steps of construction. Since the wrapped butterfly network is a growing massive structure, analysis in this network aims to establish tight bounds for secure domination and secure edge domination numbers. newline