STAR-FACTORS AND K-BOUNDED TOTAL DOMINATION

In this paper, we consider a variation of total domination in which we limit the ability of a vertex to dominate its neighbors in one of two ways: (a) Every vertex in the dominating set dominates exactly k of i ts neighbors. Graphs that have such dominating sets are characterized and a recognition algorithm for trees is described. (b) Every vertex i n the dominating set dominates no more than k of its neighbors. It is shown that the existence of such a dominating set is equivalent to the existence in the graph of a star-factor (which is a partition of the vertex set into m-stars where 1 less than or equal to m less than or e qual to k). It is further shown that the existence of such a star-fact or is equivalent to a Tutte-like condition which requires that k\N(I)\ greater than or equal to \I\ for every independent set I of vertices in G. When this last result is interpreted in the case when G is bipar tite, a generalization of the Marriage Theorem emerges. (C) 1996 John Wiley & Sons, Inc.