Zero forcing and power domination in graphs

This thesis investigates the dynamic colouring of vertices in a graph G. Dynamic colouring of the vertices in a graph has seen a rise in application and relations to well studied graph theoretic parameters in recent years. By dynamic colouring, we mean a colouring of the vertices in a graph which may propagate (change the colour of) vertices that were not initially coloured in the graph. Of these dynamic colourings, and of relation to this thesis, we highlight that zero forcing sets and power dominating sets, and the associated graph invariants known as the zero forcing number and power domination number respectively, are of particular interest. Both zero forcing number and power domination number have been shown to relate to well studied graph invariants such as the domination number, the total domination number, the connected domination number, the path cover number, the chromatic number, the independence number, and the minimum rank. Moreover, it has been established that both these problems lie within the class of NP-complete decision problems. Thus, it is desirable to find easily computable bounds for the zero forcing number and power domination number. In this thesis, we give an alternate interpretation of zero forcing and power domination problems as set covering problems. These interpretations were used in solving both these problems for de Bruijn and Kautz digraphs. Moreover the same technique was used to extend the results to obtain these graph invariants for iterated line digraphs. The zero forcing problem is solved for butter y networks and bounds were obtained in the case of power domination number. Another important result in this thesis is settling the conjecture of Davila and Kenter connecting zero forcing number, girth and minimum degree. A general lower bound technique for power domination number by looking at subgraphs satisfying certain conditions is described and used effectively in finding the power domination number of some specific graphs. In the last section of the thesis, we introduce a new variant of power domination problem called resolving-power domination problem. We show that the problem is NP-complete.