The objective of this Research Planning Grant (RPG) is to initiate the study of multiple domination in graphs. A node in a graph G=(V,E) is said to dominate itself and its neighbors. A subset of the vertices S is a dominating set if each node of V is dominated by some node of S. Interest in the concept of domination has mushroomed in the last twenty years as can be evidenced by over 500 publications on the subject. Furthermore, over 60 types of domination have been defined and studied. No doubt one reason for this interest is its many applications in computer science areas such as network design and analysis of algorithms. A recent paper introduces multiple domination as a generalization of classical domination in graphs. A set S is a k-multiple dominating set for G if each node in V is dominated by at least k distinct nodes in S. This new concept in which each node is in a sense redundantly dominated is a rich topic for research and potential applications. In general, any question asked about ordinary domination can be asked about multiple domination. This research investigates multiple domination and develops the most promising research issues for future study.
