Geodesic
Total 2-domination number in digraphs and its dual parameter
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 587-606 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A subset S of vertices of a digraph D is a total 2-dominating set if every vertex not in S is adjacent from at least two vertices in S, and the subdigraph induced by S has no isolated vertices. Let D^-1 be a digraph obtained by reversing the direction of every arc of D. In this work, we investigate this concept which can be considered as an extension of double domination in graphs G to digraphs D, along with total 2-limited packing (L_2^t(D)) of digraphs D which has close relationships with the above-mentioned concept. We prove that the problems of computing these parameters are NP-hard, even when the digraph is bipartite. We also give several lower and upper bounds on them. In dealing with these two parameters our main emphasis is on directed trees, by which we prove that L_2^t (D)+L_2^t (D^-1) can be bounded from above by 16n//9 for any digraph D of order n. Also, we bound the total 2-domination number of a directed tree from below and characterize the directed trees attaining the bound.
Keywords: total $2$-domination number, total $2$-limited packing number, directed tree 
@article{DMGT_2023_43_3_a0,
     author = {Mojdeh, Doost Ali and Samadi, Babak},
     title = {Total 2-domination number in digraphs and its dual parameter},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {587--606},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a0/}
}
TY  - JOUR
AU  - Mojdeh, Doost Ali
AU  - Samadi, Babak
TI  - Total 2-domination number in digraphs and its dual parameter
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 587
EP  - 606
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a0/
LA  - en
ID  - DMGT_2023_43_3_a0
ER  - 
%0 Journal Article
%A Mojdeh, Doost Ali
%A Samadi, Babak
%T Total 2-domination number in digraphs and its dual parameter
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 587-606
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a0/
%G en
%F DMGT_2023_43_3_a0
Mojdeh, Doost Ali; Samadi, Babak. Total 2-domination number in digraphs and its dual parameter. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 587-606. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a0/

[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546. https://doi.org/10.1016/j.dam.2011.12.018

[2] S. Arumugam, K. Jacob and L. Volkmann, Total and connected domination in digraphs, Australas. J. Combin. 39 (2007) 283–292.

[3] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, in: Springer Monogr. Math. (Springer-Verlag London Ltd., London, 2007).

[4] C. Berge, The Theory of Graphs and its Applications (Methuen, London, 1962).

[5] G. Chartrand, F. Harary and B. Quan Yue, On the out-domination and in-domination numbers of a digraph, Discrete Math. 197/198 (1999) 179–183. https://doi.org/10.1016/S0012-365X(99)90059-6

[6] X. Chen, G. Hao and L. Volkmann, Bounds on the signed Roman k-domination number of a digraph, Discuss. Math. Graph Theory 39 (2019) 67–79. https://doi.org/10.7151/dmgt.2068

[7] X. Chen, G. Hao and Z. Xie, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019) 13–21. https://doi.org/10.7151/dmgt.2067

[8] N.E. Clarke and R.P. Gallant, On 2-limited packings of complete grid graphs, Discrete Math. 340 (2017) 1705–1715. https://doi.org/10.1016/j.disc.2016.11.001

[9] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, Alavi, Chartrand, Lesniak and Wall (Ed(s)), (Wiley, New-York 1985) 283–300.

[10] Y. Fu, Dominating set and converse dominating set of a directed graph, Amer. Math. Monthly 75 (1968) 861–863. https://doi.org/10.2307/2314337

[11] M. Furuya, Bounds on the domination number of a digraph and its reverse, Filomat 32 (2018) 2517–2524. https://doi.org/10.2298/FIL1807517F

[12] R. Gallant, G. Gunther, B.L. Hartnell and D.F. Rall, Limited packing in graphs, Discrete Appl. Math. 158 (2010) 1357–1364. https://doi.org/10.1016/j.dam.2009.04.014

[13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman & Co., New York, 1979).

[14] D.S. Hochbaum and D.B. Shmoys, A best possible heuristic for the k-center problem, Math. Oper. Res. 10 (1985) 180–184. https://doi.org/10.1287/moor.10.2.180

[15] G. Hao and J. Qian, On the sum of out-domination number and in-domination number of digraphs, Ars Combin. 119 (2015) 331–337.

[16] G. Hao, J. Qian and Z. Xie, On the sum of the total domination numbers of a digraph and its converse, Quaest. Math. 42 (2019) 47–57. https://doi.org/10.2989/16073606.2018.1438531

[17] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.

[18] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[19] C. Lee, Domination in digraphs, J. Korean Math. Soc. 35 (1998) 843–853.

[20] D.A. Mojdeh, B. Samadi and I.G. Yero, Further results on packing related parameters in graphs, Discuss. Math. Graph Theory, in press. https://doi.org/10.7151/dmgt.2262

[21] D.A. Mojdeh, B. Samadi and I.G. Yero, Packing and domination parameters in digraphs, Discrete Appl. Math. 269 (2019) 184–192. https://doi.org/10.1016/j.dam.2019.04.008

[22] M. Liedloff, Finding a dominating set on bipartite graphs, Inform. Process. Lett. 107 (2008) 154–157. https://doi.org/10.1016/j.ipl.2008.02.009

[23] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175–177. https://doi.org/10.2307/2306658

[24] O. Ore, Theory of Graphs in: Amer. Math. Soc. Colloq. Publ. 38 (Amer. Math. Soc., Providence, 1962).

[25] L. Ouldrabah, M. Blidia and A. Bouchou, On the k-domination number of digraphs, J. Comb. Optim. 38 (2019) 680–688. https://doi.org/10.1007/s10878-019-00405-1

[26] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, USA, 2001).