Proper 3-Dominating Sets in Graphs

Abstract

A dominating set is a classic concept that is widely used in road safety, disaster rescue operations, and chemical graphs. In this paper, we introduce a variation of the dominating set: the proper 3-dominating set. For a proper 3-dominating set D of graph G, any vertex outside D is adjacent to at least three vertices inside D, and there exists one vertex outside D that is adjacent to three vertices inside D. For graph G, the proper 3-domination number is the minimum cardinality among all proper 3-dominating sets of G. We find that a graph with minimum degree at least 3 or one for which there exists a subgraph with some characteristic always contains a proper 3-dominating set. Further, we find that when certain conditions are met, some graph products, such as the joint product, strong product, lexicographic product, and corona product of two graphs, have a proper 3-dominating set. Moreover, we discover the bounds of the proper 3-domination number. For some special graphs, we get their proper 3-domination numbers.

Keywords

• domination number
• dominating set
• 3-dominating set
• proper 3-dominating set