Independent domination in directed graphs

Document Type : Original paper


1 West Virginia University

2 Virginia Commonwealth University

3 Department of Mathematics, Sri Venkateswara College of Engineering


In this paper we initialize the study of independent domination in directed graphs. We show that an independent dominating set of an orientation of a graph is also an independent dominating set of the underlying graph, but that the converse is not true in general. We then prove existence and uniqueness theorems for several classes of digraphs including orientations of complete graphs, paths, trees, DAGs, cycles, and bipartite graphs. We also provide the idomatic number for special cases of some of these families of digraphs.


Main Subjects

[1] S. Bau, N.C. Wormald, and S. Zhou, Decycling numbers of random regular graphs, Random Structures & Algorithms 21 (2002), no. 3-4, 397–413.
[2] M. Cary, Dominator chromatic numbers of orientations of trees, arXiv preprint arXiv:1904.06293 (2019).
[3] , Dominator colorings of digraphs, Open J. Discrete Appl. Math. 3 (2020), no. 2, 50–67.
[4] E.J. Cockayne, G. Fricke, and C.M. Mynhardt, On a nordhaus-gaddum type problem for independent domination, Discrete Math. 138 (1995), no. 1-3, 199–205.
[5] E.J. Cockayne and S.T. Hedetniemi, Disjoint independent dominating sets in graphs, Discrete Math. 15 (1976), no. 3, 213–222.
[6] F. Dai and J. Wu, On constructing k-connected k-dominating set in wireless ad hoc and sensor networks, Journal of parallel and distributed computing 66 (2006), no. 7, 947–958.
[7] W. Duckworth and N.C. Wormald, Minimum independent dominating sets of random cubic graphs, Random Structures & Algorithms 21 (2002), no. 2, 147–161.
[8] , On the independent domination number of random regular graphs, Combin. Probab. Comput. 15 (2006), no. 4, 513–522.
[9] J.E. Dunbar, D.J. Erwin, T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Broadcasts in graphs, Discrete Appl. Math. 154 (2006), no. 1, 59–75.
[10] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984), no. 2, 115–130.
[11] O. Favaron, A bound on the independent domination number of a tree, vol. 1, Universit´e Paris-Sud, Centre d’Orsay, Laboratoire de recherche en Informatique, 1992.
[12] R. Gera, On dominator colorings in graphs, Graph Theory Notes N. Y. 52 (2007), 25–30.
[13] N.I. Glebov and A.V. Kostochka, On the independent domination number of graphs with given minimum degree, Discrete Math. 188 (1998), no. 1-3, 261–266.
[14] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), no. 7, 839–854.
[15] T.W. Haynes, S.T. Hedetniemi, and P. Slater, Domination in graphs: Advanced topics, Routledge, 1998.
[16] T.W. Haynes, S.T. Hedetniemi, and P. Slater, Fundamentals of domination in graphs, CRC press, 1998.
[17] R.W. Irving, On approximating the minimum independent dominating set, Inform. Process. Lett. 37 (1991), no. 4, 197–200.
[18] De-X. Ma and Xue-G. Chen, A note on connected bipartite graphs having independent domination number half their order, Appl. Math. lett. 17 (2004), no. 8, 959–962.
[19] S. Prabhu, T. Flora, and M. Arulperumjothi, On independent resolving number of $TiO_2[m, n]$ nanotubes, Journal Intell. Fuzzy Syst. 33 (2018), no. 6, 6421–6425.
[20] Z. Shao, Z. Li, A. Peperko, J. Wan, and J. Ĺ˝erovnik,  Independent rainbow domination of graphs, Bull. Malays. Math. Sci. Soc. 42 (2019), no. 2, 417–435.
[21] L. Sun and J. Wang, An upper bound for the independent domination number, J. Combin. Theory Ser. B 76 (1999), no. 2, 240–246.
[22] M. Valencia-Pabon, Idomatic partitions of direct products of complete graphs, Discrete Math. 310 (2010), no. 5, 1118–1122.
[23] J. Wu, M. Cardei, F. Dai, and S. Yang, Extended dominating set and its applications in ad hoc networks using cooperative communication, IEEE Trans. Parallel Distrib. Syst. 17 (2006), no. 8, 851–864.
[24] J. Wu and H. Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, Citeseer, 1999, pp. 7–14.
[25] B. Zelinka, Adomatic and idomatic numbers of graphs, Math. Slovaca 33 (1983), no. 1, 99–103.