Given a positive integer @math , a @math -dominating set in a graph @math is a set of vertices such that every vertex not in the set has at least @math neighbors in the set. A total @math -dominating set, also known as a @math -tuple total dominating set, is a set of vertices such that every vertex of the graph has at least @math neighbors in the set. The problems of finding the minimum size of a @math -dominating, resp. total @math -dominating set, in a given graph, are referred to as @math -domination, resp. total @math -domination. These generalizations of the classical domination and total domination problems are known to be NP-hard in the class of chordal graphs, and, more specifically, even in the classes of split graphs (both problems) and undirected path graphs (in the case of total @math -domination). On the other hand, it follows from recent work by (2017) that these two families of problems are solvable in time @math in the class of interval graphs. In this work, we develop faster algorithms for @math -domination and total @math -domination in the class of proper interval graphs. The algorithms run in time @math for each fixed @math and are also applicable to the weighted case.
The works of Liao and Chang @cite_41 and of Lee and Chang @cite_7 consider various domination problems in the class of strongly chordal graphs (and, in the case of @cite_41 , also dually chordal graphs). While the class of strongly chordal graphs generalizes the class of interval graphs, the domination problems studied in @cite_41 @cite_7 all deal with closed neighborhoods, and for those cases structural properties of strongly chordal and dually chordal graphs are helpful for the design of linear-time algorithms. In contrast, @math -domination and total @math -domination are defined via open neighborhoods and results of @cite_41 @cite_7 do not seem to be applicable or easily adaptable to our setting.
@cite_41 @cite_7
2017926358 2068218174
In 1985, Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs. For a positive integer k, a subset S of vertices in a graph G = (V, E) is k-dominating if every vertex of V − S is adjacent to at least k vertices in S. The subset S is k-independent if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. In this paper we survey results on k-domination and k-independence. Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V->Y such that @?"u"@?"N"""G"["v"]f(u)>=1 for all vertices [email protected]?V, where N"G[v]= v @? u|(u,v)@?E . Let f(S)[email protected]?"u"@?"Sf(u) for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as k -domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the k -domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.