Partitioning vertices into in- and out-dominating sets in digraphs
Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Let \(D\) be a digraph with the vertex set \(V(D)\) and the arc set \(A(D)\). A set \(X\subseteq V(D)\) is an out-dominating set if every vertex not in \(X\) is adjacent from a vertex in \(X\). Similarly, a set \(X\subseteq V(D)\) is an in-dominating set if every vertex not in \(X\) is adjacent to a vertex in \(X\). Directed \(p\)-in \(q\)-out domatic partition is the problem that given a digraph \(D\) and positive integers \(p\) and \(q\), determines whether there exists a partition of the vertex set \(V(D)=I_1\cup\cdots\cup I_p\cup O_1\cup\cdots\cup O_q\) such that \(I_i\) are in-dominating sets of \(D\) for \(1\leq i\leq p\) and \(O_j\) are out-dominating sets of \(D\) for \(1\leq j\leq q\). The IOP problem is the problem that given a digraph \(D\), determines whether there exists a partition of the vertex set \(V(D)=I\cup O\) such that \(I\) is an in-dominating set and \(O\) is an out-dominating sets of \(D\). In this article, the authors posed the problem of directed \(p\)-in \(q\)-out domatic partition, which is a domatic partition problem for digraphs, and investigated the problem whether a given digraph has a partition of the vertices into in- and out-dominating sets. The authors derived the following results: (1) the IOP problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a linear-time algorithm for deciding the existence of such partition. In fact, it would be interesting to discuss the directed \(p\)-in \(q\)-out domatic partition for various kinds of digraphs.
- Connected k-tuple twin domination in de Bruijn and Kautz digraphs
- Digraphs
- Graphs \& digraphs
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1302196 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 1124608 (Why is no real title available?)
- scientific article; zbMATH DE number 2191983 (Why is no real title available?)
- Kernels in planar digraphs
- On the (h,k)-domination numbers of iterated line digraphs
- On the out-domination and in-domination numbers of a digraph
- Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
- The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs
- Towards a theory of domination in graphs
- Out-degree reducing partitions of digraphs
- Partitioning the vertices of a cubic graph into two total dominating sets
- On the parameterized complexity of 2-partitions
- The algorithmic complexity of domination digraphs
- Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
- Mod-2 independence and domination in graphs
- Partitioning the vertex set of an acyclic directed graph into convex subsets
- Safe sets and in-dominating sets in digraphs
This page was built for publication: Partitioning vertices into in- and out-dominating sets in digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197403)
