In-domination and out-domination numbers of unidirectional graphs
Sanal Kumardrssanalkumar@gmail.comDepartment of Sciences and MathematicsFaculty of MathematicsUniversity of Technology and Applied SciencesSultanate of OmanView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Jun 2023
- Published Online:
- 17 Jul 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-2701
- Pages:
- 2897–2904
Abstract
The diverging unidirectional star graph is the unidirectional star graph with n+1 nodes(vertices) and n arcs, n nodes of in-degree 1 and out-degree 0. The converging unidirectional graph consisting of n+1 vertices and n arcs, where n vertices have out-degree one and in-degree zero, with all arcs oriented towards the single central vertex. A diverging unidirectional perfect binary tree is a directed tree where each internal vertex, except for the root, has an out-degree of two and in-degree of one, with all leaves at the same depth; conversely, a converging unidirectional perfect tree has the opposite structure. Here, we investigate the in-domination and out-domination numbers associated with these classes of directed graph. Explicit expressions for the same numbers are derived for the afore mentioned families of graphs as well as for unidirectional non-homogeneous super caterpillar graphs.
Keywords
Subject Classifications
References
[1] J.F. Couturier, R. Letourneur, and M. Liedloff, “On the number of minimal dominating sets on some graph classes,” Theoretical Computer Science, vol. 562, pp. 634–642 (2015).
[2] J. Ghoshal, R. Laskar, and D. Pillone, Domination in Graphs, 1st ed. New York, NY, USA: Routledge (1998).
[3] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, 1st ed, CRC Press, Boca Raton (1998). doi.org/10.1201/9781482246582
[4] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Eds., Domination in Graphs: Advanced Topics, 1st ed, CRC Press, Boca Raton (1998). doi.org/10.1201/9781315141428
[5] S. Alikhani, “Dominating Sets and Domination Polynomials of Graphs”, LAP Lambert Academic Publishing, Saarbrücken, Germany (Jan. 2012).
[6] D. G. Corneil and Y. Perl, “Clustering and domination in perfect graphs,” Discrete Applied Mathematics, vol. 9, no. 1, pp. 27–39 (Sept. 1984).
[7] P. P. Hawkins, A. M. Anto, and T. S. I. Mary, “Perfect dominating sets and perfect domination polynomial of a pan graph,” Journal of Critical Reviews, vol. 7, no. 4 (2020).
[8] A. Brandstadt and D. Kratsch, “On domination problems for permutation and other graphs,” Theoretical Computer Science, vol. 54, no. 2–3, pp. 181–198 (1987).
[9] B. K. P. Arimbawa and E. T. Baskoro, “Partition dimension of some classes of trees,” Procedia Computer Science, vol. 74, pp. 67–72 (2015).
[10] G. Mahadevan and V. Vijayalakshmi, “Clone hop domination number of a graph,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 22, no. 5, pp. 719–729 (2019), doi: 10.1080/09720529.2019.1681689.
[11] M. Hashemipour, M. R. Hooshmandasl, and A. Shakiba, “On the outer-connected domination number for graph products,” Journal of Information and Optimization Sciences, vol. 41, no. 5, pp. 1253–1267 (2020), doi: 10.1080/02522667.2019. 1645396.
[12] J. Ghoshal, R. Laskar, and D. Pillone, “Topics on domination in directed graphs,” in Domination in Graphs. New York, NY, USA: Routledge, pp. 401–437 (1998).
[13] C. Pang, R. Zhang, Q. Zhang, and J. Wang, “Dominating sets in directed graphs,” Information Sciences, vol. 180, no. 19, pp. 3647–3652 (2010).
[14] G. Chartrand, F. Harary, and B. Q. Yue, “On the out-domination and in-domination numbers of a digraph,” Discrete Mathematics, vol. 197–198, pp. 179–183 (1999).
