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 m-stars where 1 ≤ m ≤ k). It is further shown that the existence of such a star-factor is equivalent to a Tutte-like condition which requires that k|N(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. © 1996 John Wiley & Sons, Inc.

Abstract This paper considers the following variation on the construction of a reliable communication network. Whenever a vertex is attacked, all vertices within distance 2 are also destroyed (or fail) indirectly. We are interested in designing a connected graph (undirected, all edges of length one) on p vertices such that when a random subset of the vertices are attacked the expected number of vertices that are destroyed (directly and indirectly) is minimized. It is assumed that any of the 2p subsets of vertices is equally likely to be attacked. The optimal structure is determined for all p and is shown to be one of five patterns depending on r where p = 5t + r.

Abstract In [G. Gunther, Neighbor‐connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243] Gunther introduced the concept of a k neighbor‐connected graph, which has the property that the removal of any k − 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that are k‐regular in addition to being k neighbor‐connected. In a private communication, Gunther conjectured that if G is such a graph which contains no cliques of size larger than m, then |V(G)| ≧ k2 + (k + 1 − m) (k − 1) + 1. In the above reference, he proved that this conjecture is valid in the case that m = k and characterized the minimal graphs. In this paper, we begin to investigate the case where m = 2. We give some results connecting the minimal graphs to other combinatorial objects.