Variant of forcing sets in interconnection networks

Abstract

This thesis analyses the dynamic monitoring of vertices in a graph G. newlineBy dynamic monitoring we mean the choice of vertices in a graph which may newlineinfect or monitor vertices which were not initially monitored in the graph newlinebased on certain conditions. Of these dynamic monitoring, we highlight only newlinethe power domination set and the zero forcing set to define the edge-forcing newlineset and P3-forcing set together with the associated graph parameters namely newlinethe edge-forcing number and the P3-forcing number. The Edge-forcing newlineproblem is to determine the edge-forcing number. We have proved that the edgeforcing newlineproblem is NP-complete. The edge-forcing problem and the P3-forcing newlineproblem have been studied for several classes of graphs such as Butterfly newlineNetworks, Honeycomb Networks, Triangular Grid Networks, Tree-like newlinearchitectures and Sierpinski-like graphs. Sharp lower bounds for edge-forcing newlinenumber have been obtained for certain dimensions of Butterfly Network, newlinee(BF(3)) = 8, e(BF(4)) = 25 and e(BF(5)) = 47. In the last section, we newlineintroduce an application of the edge-forcing problem, in which the edgeforcing newlineset acts as a virtual backbone in a wireless sensor environment where newlinethe water contamination event has to be detected based on the water newlineparameters. A supervised machine learning algorithm is applied, the quality of newlinewater determined and viewed on a graphical scale newline newline