Geodesic
Total 2-domination number in digraphs and its dual parameter
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 587-606

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {43},
     number = {3},
     year = {2023},
     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
PB  - mathdoc
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
%I mathdoc
%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/