Star-factors andk-bounded total domination

✍ Scribed by Gunther, Georg; Hartnell, Bert; Rall, Douglas

• Book ID: 101225035
• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 492 KB
• Volume: 27
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199605)27:3<197::aid-net4>3.0.co;2-d

✦ Synopsis

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 its neighbors. Graphs that have such dominating sets are characterized and a recognition algorithm for trees is described. (b) Every vertex in 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 rn-stars where 1 I m I k). It is further shown that the existence of such a star-factor is equivalent to a Tutte-like condition which requires that k I N ( I ) I 2 I I I for every independent set I of vertices in G. When this last result is interpreted in the case when G is bipartite, a generalization of the Marriage Theorem emerges.