×

Partitioning vertices into in- and out-dominating sets in digraphs. (English) Zbl 1451.05193

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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Araki, T., The \(k\)-tuple twin domination in de Bruijn and Kautz digraphs, Discrete Math., 308, 6406-6413 (2008), URL http://dx.doi.org/10.1016/j.disc.2007.12.020 · Zbl 1180.05079
[2] Araki, T., Connected twin domination in de Bruijn and Kautz digraphs, Discrete Math., 309, 6229-6234 (2009), URL http://dx.doi.org/10.1016/j.disc.2009.05.031 · Zbl 1210.05092
[3] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2009), Springer-Verlag: Springer-Verlag London · Zbl 1170.05002
[4] Chang, G. J., Algorithmic aspects of domination in graphs, (Du, D.; Pardalos, P., Handbook of Combinatorial Optimization, Vol. 3 (1998), Kluwer Academic Publishers), 339-405 · Zbl 1058.90524
[5] Chartrand, G.; Dankelmann, P.; Schultz, M.; Swart, H. C., Twin domination in digraphs, Ars Combin., 67, 105-114 (2003) · Zbl 1079.05064
[6] Chartrand, G.; Harary, F.; Yue, B. Q., On the out-domination and in-domination numbers of a digraph, Discrete Math., 197-198, 179-183 (1999) · Zbl 0978.05057
[7] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs & Digraphs (2011), Chapman & Hall/CRC · Zbl 1211.05001
[8] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051
[9] Fraenkel, A. S., Planar kernel and grundy with \(d \leq 3, d^+ \leq 2, d^- \leq 2\) are NP-complete, Discrete Appl. Math., 3, 257-262 (1981) · Zbl 0493.68040
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide To the Theory of NP-Completeness (1979), W.H. Freeman & Co. Now York: W.H. Freeman & Co. Now York NY, USA · Zbl 0411.68039
[11] Ghosal, J.; Laskar, R.; Pillone, D., Topics on domination in directed graphs, (Haynes, T.; Hedetniemi, S.; Slater, P., Domination in Graphs: Advanced Topics (1998), Marcel Dekker), 401-437 · Zbl 0887.05029
[12] Gutin, G.; Kloks, T.; Lee, C. M.; Yeo, A., Kernels in planar digraphs, J. Comput. System Sci., 71, 174-184 (2005) · Zbl 1170.68547
[13] Hasunuma, T.; Otani, M., On the \(( h , k )\)-domination numbers of iterated line digraphs, Discrete Appl. Math., 160, 12, 1859-1863 (2012), URL http://dx.doi.org/10.1016/j.dam.2012.03.024 · Zbl 1246.05118
[14] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0883.00011
[15] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[16] Ore, O., Theory of Graphs (1962), Amer. Math. Soc. Colloq. Publ.: Amer. Math. Soc. Colloq. Publ. Providence, RI
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.