DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

D.A. Mojdeh

Doost Ali Mojdeh

Department of MathematicsUniversity of MazandaranBabolsar P.O. Box 47416-1467IRAN

email: damojdeh@umz.ac.ir

0000-0001-9373-3390

B. Samadi

Babak Samadi

email: samadibabak62@gmail.com

Title:

Total 2-domination number in digraphs and its dual parameter

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 587-606

Received: 2020-05-07 , Revised: 2020-11-19 , Accepted: 2020-11-26 , Available online: 2020-12-31 , https://doi.org/10.7151/dmgt.2387

Abstract:

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^{t}_{2}(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^{t}_{2}(D)+L^{t}_{2}(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

References:

  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).
Close