Domination cover number of graphs

Abstract

A set D ⊆ V for the graph G = (V,E) is called a dominating set if any vertex v ∈ V\D has at least one neighbor in D. Fomin et al. [Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Transactions on Algorithms (TALG) 5(1) (2008) 9] gave an algorithm for enumerating all minimal dominating sets with n vertices in O(1.7159 n ) time. It is known that the number of minimal dominating sets for interval graphs and trees on n vertices is at most 3 n/3 ≈ 1.4422 n . In this paper, we introduce the domination cover number as a new criterion for evaluating the dominating sets in graphs. The domination cover number of a dominating set D, denoted by C D (G), is the summation of the degrees of the vertices in D. Maximizing or minimizing this parameter among all minimal dominating sets has interesting applications in many real-world problems, such as the art gallery problem. Moreover, we investigate this concept for different graph classes and propose some algorithms for finding the domination cover number in trees and block graphs. © 2019 World Scientific Publishing Company.