A Maximum Dicut in a Digraph Induced by a Minimal Dominating Set
V. V. Voroshilov · Journal of Applied and Industrial Mathematics · 2020
Let $$G = (V,A)$$ be a simple directed graph and let $$S\subseteq V $$ be a subset of the vertex set $$V $$ . The set $$S $$ is called dominating if for each vertex $$j\in V\setminus S$$ there exist at least one $$i\in S $$ and an edge from $$i $$ to $$j$$ . A dominating set is called (inclusion) minimal if it contains no smaller dominating set. A dicut $$\{S\rightarrow \overline {S}\} $$ is a set of edges $$(i,j)\in A $$ such that $$i\in S $$ and $$j\in V\setminus S $$ . The weight of a dicut is the total weight of all its edges. The article deals with the problem of finding a dicut $$\{S\rightarrow \overline {S}\} $$ with maximum weight among all minimal dominating sets.