Each vertex of a graph \(G = (V, E)\) dominates every vertex in its closed neighborhood. A set \(S \subset V\) is a dominating set if each vertex in \(V\) is dominated by at least one vertex of \(S\), and is an \({efficient\; dominating\; set}\) if each vertex in \(V\) is dominated by exactly one vertex of \(S\).The domination excess \(de(G)\) is the smallest number of times that the vertices of \(G\) are dominated more than once by a minimum dominating set.
We study graphs having efficient dominating sets. In particular, we characterize such coronas and caterpillars, as well as the graphs \(G\) for which both \(G\) and \(\bar{G}\) have efficient dominating sets.Then we investigate bounds on the domination excess in graphs which do not have efficient dominating sets and show that for any tree \(T\) of order \(n\),
\(de(T) \leq \frac{2n}{3} – 2\).

Let \(G = (V, E)\) be a graph. A vertex \(u\) strongly dominates a vertex \(v\) if \(uv \in E\) and \(\deg(u) > \deg(v)\). A set \(S \subseteq V\) is a strong dominating set of \(G\) if every vertex in \(V – S\) is strongly dominated by at least one vertex of \(S\).The minimum cardinality among all strong dominating sets of \(G\) is called the strong domination number of \(G\) and is denoted by \(\gamma_{st}(G)\). This parameter was introduced by Sampathkumar and Pushpa Latha in [4].In this paper, we investigate sharp upper bounds on the strong domination number for a tree and a connected graph. We show that for any tree \(T\) of order \(p > 2\) that is different from the tree obtained from a star \(K_{1,3}\) by subdividing each edge once,
\(\gamma_{st}(T) \leq \frac{4p – 1}{7}\) and this bound is sharp.For any connected graph \(G\) of order \(p \geq 3\), it is shown that \(\gamma_{st}(G) \leq \frac{2(p – 1)}{3}\) and this bound is sharp. We show that the decision problem corresponding to the computation of \(\gamma_{st}\) is NP-complete, even for bipartite or chordal graphs.

Let \(V\) be a finite set of order \(\nu\). A \((\nu, \kappa\lambda)\) packing design of index \(\lambda\) and block size \(\kappa\) is a collection of \(\kappa\)-element subsets, called blocks, such that every 2-subset of \(V\) occurs in at most \(\lambda\) blocks.The packing problem is to determine the maximum number of blocks, \(\sigma(\nu\kappa\lambda)\), in a packing design. It is well known that \(\sigma(\nu, \kappa\lambda) \leq \left[\frac{\nu}{\kappa}\left[ \frac{(\nu-1)}{(\kappa-1)}\lambda\right]\right] = \Psi(\nu, \kappa, \lambda)\), where \([x]\) is the largest integer satisfying \(x \geq [x]\).It is shown here that \(\sigma(\nu, 5, \lambda) = \Psi(\nu, 5, \lambda) – e\) for all positive integers \(\nu \geq 5\) and \(7 \leq \lambda \leq 21\), where \(e = 1\text{ if } \lambda(\nu-1) \equiv 0 \pmod{\kappa-1} \text{ and } \lambda\nu\frac{(\nu-1)}{(\kappa-1)} \equiv 1 \pmod{\kappa}\) and \(e = 0\) otherwise with the following possible exceptions of \((\nu, \lambda)\) = (28,7), (32,7), (44,7), (32,9), (28,11), (39,11), (28,13), (28,15), (28,19), (39,21).

A covering of the complete directed symmetric graph \(DK_v\) by \(m\)-circuits, denoted by \((v,m) – {DCC}\), is a family of \(m\)-circuits in \(DK_v\) whose union is \(DK_v\). The covering number \(C(v,m)\) is the minimum number of \(m\)-circuits in such a covering.The covering problem is to determine the value \(C(v,m)\) for every integer \(v \geq m\). In this paper, the problem is reduced to the case \(m+5 \leq v \leq 2m – 4\), for any fixed even integer \(m \geq 4\).In particular, the values of \(C(v,m)\) are completely determined for \(m = 12, 14,\) and \(16\). Additionally, a directed construction of optimal \((6k + 11, 4k + 6) – {DCC}\) is given.

It is shown that if \(H\) is a connected graph obtained from \(H_1\) and \(H_2\) by joining them with a bridge, then \(r(K_k, H) \leq r(K_k, H_1) + r(K_k, H_2) + k – 2\). We give some applications of this result.

Two closely related types of vertex subsets of a graph, namely external redundant sets and weak external redundant sets, together with associated parameters, are discussed. Both types may be used to characterize those irredundant subsets of a graph which are maximal.

Let \(G\) be a graph and let \(S\) be a subset of vertices of \(G\). A vertex \(v\) of \(G\) is called perfect with respect to \(S\) if \(|N[v] \cap S| = 1\), where \(N[v]\) denotes the closed neighborhood of \(v\). The set \(S\) is defined to be a perfect neighborhood set of \(G\) if every vertex of \(G\) is perfect or adjacent with a perfect vertex.The perfect neighborhood number \(\theta(G)\) of \(G\) is defined to be the minimum cardinality among all perfect neighborhood sets of \(G\). In this paper, we present a variety of algorithmic results on the complexity of perfect neighborhood sets in graphs.

We consider the problem of sweeping (or grazing) the interior/exterior of a polygon by a flexible rope whose one endpoint (anchor) is attached on the boundary of the polygon. We present a linear-time algorithm to compute the grazing area inside a simple polygon. We show how to extend the algorithm for computing the internal grazing area, without increasing its time complexity, to compute the grazing area in the exterior of a simple polygon. For grazing in the exterior of a convex polygon, we present an \(O(n)\) time algorithm to locate the anchor point that maximizes the simple grazing area. All three algorithms are optimal within a constant factor. Grazing area problems can be viewed as guard placement problems under \(L\)-visibility.

Forming all distinct subsets with \(k\) or fewer objects from a set with \(n\) elements can be accomplished by generating a subset of the binary reflected Gray code. This paper presents a straightforward algorithm that generates the desired Gray codewords by altering the stack which maintains the transition sequence that determines the next codeword position to be altered.

A vertex of a graph \(G\) dominates itself and its neighbors. A set \(S\) of vertices of \(G\) is a dominating set if each vertex of \(G\) is dominated by some vertex of \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A minimum dominating set is one of cardinality \(\gamma(G)\). A subset \(T\) of a minimum dominating set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum dominating set containing \(T\). The forcing domination number \(f(S, \gamma)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\), and the forcing domination number \(f(G, \gamma)\) of \(G\) is the minimum forcing domination number among the minimum dominating sets of \(G\). For every graph \(G\), \(f(G, \gamma) \leq \gamma(G)\).It is shown that for integers \(a, b\) with \(b\) positive and \(0 \leq a \leq b\), there exists a graph \(G\) such that \(f(G, \gamma) = a\) and \(\gamma(G) = b\). The forcing domination numbers of several classes of graphs are determined, including complete multipartite graphs, paths, cycles, ladders, and prisms. The forcing domination number of the cartesian product \(G\) of \(k\) copies of the cycle \(C_{2k+1}\) is studied. Viewing the graph \(G\) as a Cayley graph, we consider the algebraic aspects of minimum dominating sets in \(G\) and forcing subsets.