1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Total 2-Domination Number in Digraphs and Its Dual Parameter

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 May 2020
Accepted: 26 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 (Lt2(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 Lt2(D) + Lt2(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

MSC 2010

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

[2] S. Arumugam, K. Jacob and L. Volkmann, Total and connected domination in di-graphs, Australas. J. Combin. 39 (2007) 283–292.Search in Google Scholar

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

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

[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. doi:10.1016/S0012-365X(99)90059-610.1016/S0012-365X(99)90059-6Search in Google Scholar

[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. doi:10.7151/dmgt.206810.7151/dmgt.2068Search in Google Scholar

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

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

[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.Search in Google Scholar

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

[11] M. Furuya, Bounds on the domination number of a digraph and its reverse, Filomat 32 (2018) 2517–2524. doi:10.2298/FIL1807517F10.2298/FIL1807517FSearch in Google Scholar

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

[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).Search in Google Scholar

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

[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.Search in Google Scholar

[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. doi:10.2989/16073606.2018.143853110.2989/16073606.2018.1438531Search in Google Scholar

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

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

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

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

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

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

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

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

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

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

Recommended articles from Trend MD

Plan your remote conference with Sciendo