Disjoint dominating sets with a perfect matching
William F. Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello · Discrete Mathematics Algorithms and Applications · 2017
In this paper, we consider dominating sets [Formula: see text] and [Formula: see text] such that [Formula: see text] and [Formula: see text] are disjoint and there exists a perfect matching between them. Let [Formula: see text] denote the cardinality of smallest such sets [Formula: see text] in [Formula: see text] (provided they exist, otherwise [Formula: see text]). This concept was introduced in [W. F. Klostermeyer, M. E. Messinger and A. Angeli Ayello, An eternal domination problem in grids, Theory Appl. Graphs 4(1) (2017) 23pp.] in the context of studying a certain graph protection problem. We characterize the trees [Formula: see text] for which [Formula: see text] equals a certain graph protection parameter and for which [Formula: see text], where [Formula: see text] is the independence number of [Formula: see text]. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number.