Variants of forcing sets in interconnection networks

Abstract

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