Partitioning vertices into in- and out-dominating sets in digraphs
type: Item
instance of: scholarly article
title: Partitioning vertices into in- and out-dominating sets in digraphs
zbMATH Open document ID: 1451.05193
author: Kosuke Nakamura
author: Toru Araki
published in: Discrete Applied Mathematics
publication date: 2020-08-31T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7242073
zbMATH Keywords: graph algorithm
zbMATH Keywords: domination
zbMATH Keywords: digraph
zbMATH Keywords: in-domination
zbMATH Keywords: out-domination
zbMATH Keywords: domatic partition
reviewed by: Sizhong Zhou
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2020.05.021
OpenAlex ID: W3035676160
cites work: The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs
cites work: Connected \(k\)-tuple twin domination in de Bruijn and Kautz digraphs
cites work: Digraphs
cites work: Q4247463
cites work: Q5463344
cites work: On the out-domination and in-domination numbers of a digraph
cites work: Q3065457
cites work: Towards a theory of domination in graphs
cites work: Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
cites work: Q4198056
cites work: Q4378637
cites work: Kernels in planar digraphs
cites work: On the \((h,k)\)-domination numbers of iterated line digraphs
cites work: Q4368729
cites work: Q4368728
cites work: Q3291034
DOI: 10.1016/J.DAM.2020.05.021
description: scientific article; zbMATH DE number 7242073