INVERSE AND CONNECTED DOMINATION IN HYPERTREE NETWORKS

Year 2026, Volume: 16 Issue: 3, 386 - 396, 17.03.2026

V. Shalini Indra Rajasingh

https://izlik.org/JA88TL54XX

Abstract

A dominating set of a graph \( G = (V, E) \) is a subset $D$ of vertices such that every vertex in \( V \setminus D \) is adjacent to at least one vertex in \( D \), and the minimum size of such a set is called the domination number denoted by \( \gamma(G) \). If \( D \) is a minimum dominating set of \( G \) and there exists a dominating set \( D' \) within \( V \setminus D \), then \( D' \) is called an inverse dominating set with respect to \( D \). The minimum cardinality of such a set is known as the inverse domination number, denoted by \( \gamma'(G) \). A dominating set \( D \) is called a connected dominating set if the induced subgraph \( \langle D \rangle \) is connected in \( G \). The minimum cardinality of a connected dominating set is called the connected domination number, denoted by \( \gamma_{c}(G) \). In this paper, we have computed the inverse and connected domination numbers for Hypertree Networks.

Keywords

Domination , Inverse Domiantion , Connected Domination , Hypertree Network

References

• Talebi, Y. and Rashmanlou, H., (2019), New concepts of domination sets in vague graphs with applications, International Journal of Computing Science and Mathematics, 10(4), pp. 375–389.
• Siegel, H, J. and Stunkel, C, B., (1996), Inside parallel computers: Trends in interconnection networks, IEEE Comput, Sci, Eng., 3(3), pp. 69–71.
• Haynes, T, W., Hedetniemi, S, T. and Slater, P, J., (1998), Fundamentals of domination in graphs, Pure and Applied Mathematics.
• Sampathkumar, E. and Walikar, H, B., (1979), The connected domination number of a graph, J, Math, Phys.
• Das, B. and Bharghavan, V., (1997), Routing in ad-hoc networks using minimum connected dominating sets, Proceedings of ICC’97 - International Conference on Communications, IEEE, 1, pp. 376–380.
• Li, D., Du, H., Wan, P, J., Gao, X., Zhang, Z. and Wu, W., (2009), Construction of strongly connected dominating sets in asymmetric multihop wireless networks, Theoretical Computer Science, 410(8–10), pp. 661–669.
• Wu, J. and Li, H., (1999), 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, pp. 7–14.
• Garey, M, R. and Johnson, D, S., (1978), Computers and intractability: A guide to the theory of NP-completeness, W, H, Freeman.
• Kulli, V. and Sigarkanti, S, C., (1991), Inverse domination in graphs, National Academy Science Letters, 14.
• Domke, G, S., Dunbar, J, E. and Markus, L, R., (2004), The inverse domination number of a graph, Ars Combinatoria, 72, pp. 149–160.
• Frendrup, A., Henning, M, A., Randerath, B. and Vestergaard, P, D., (2009), On a conjecture about inverse domination in graphs.
• Chelvam, T, T. and Prema, G, S, G., (2010), Equality of domination and inverse domination numbers, Ars Combinatoria, 95, pp. 103–111.
• Cynthia, V. and Kavitha, A., (2020), Inverse domination number of circulant graph G(n; ±1,2,3). Advances & Applications in Discrete Mathematics, 23(2).
• Rajasingh, I., Jayagopal, R. and Rajan, R, S., (2020), Domination parameters in hypertrees and sibling trees, Discrete Applied Mathematics, 280, pp. 237–245.
• Shalini, V. and Rajasingh, I., (2020), Domination and inverse domination in wrapped butterfly networks, Computer Science, 15(4), pp. 1055–1063.
• Shalini, V. and Rajasingh, I., (2021), Total and inverse domination numbers of certain graphs, IOP Conference Series: Materials Science and Engineering, 1012, p.012066. IOP Publishing.
• Shalini, V. and Rajasingh, I., (2024), Inverse domination in X-trees and sibling trees, European Journal of Pure and Applied Mathematics, 17(2), pp. 1082–1093.
• Goodman, J, R. and S´equin, C, H., (1981), Hypertree: A multiprocessor interconnection topology, IEEE Transactions on Computers, C-30, pp. 923–933.
• Sundara Rajan, R., Jeyagopal, R., Rajasingh, I., Rajalaxmi, T, M. and Parthiban, N., (2015), Combinatorial properties of Root-fault hypertree, Procedia Computer Science, 57, pp. 1096–1103.
• Wardani, A, A., Ratnasari, L., Utomo, R, H, S. and Khabibah, S., (2024), Inverse domination number and inverse total domination of Sierpinski star graph, International Journal of Mathematics and Statistics Studies, 12(3), pp. 71–79.
• Klamt, S., Haus, U.-U. and Theis, F., (2009), Hypergraphs and cellular networks, PLoS Computational Biology, 5(5), p.e1000385.
• Zhou, X., Li, W. and Zhang, Y., (2021), Hypertree-based scalable clustering for large-scale data analytics, IEEE Transactions on Big Data, 7(4), pp. 856–869. Goodman, S. and Hedetniemi, S, T., (1973), Hypertrees, Congressus Numerantium, 6, pp. 87–94.
• Chekuri, C. and Rajaraman, A., (2000), Conjunctive query containment revisited, Proceedings of the 6th International Conference on Database Theory (ICDT), pp. 56–70.
• Flum, J., Grohe, M. and Marx, D., (2002), Parameterized complexity and subexponential time, Bulletin of the EATCS, 77, pp. 71–100.
• Gottlob, G., Scarcello, F. and Sideri, M., (2017), A decomposition method for constraint satisfaction and conjunctive queries, Journal of the ACM (JACM), 64(3), pp. 1–45.
• Caro, Y. and Hansberg, A., (2000), Spanning trees with many leaves and the connected domination number, Discussiones Mathematicae Graph Theory, 20(2), pp. 205–218.
• Chen, G, H., (2004), On k-γc-critical graphs and a relationship between total and connected domination in graphs, Ars Combinatoria, 72, pp. 193–204.
• Duckworth, W. and Wormald, N, C., (2009), Small connected dominating sets in regular graphs, Journal of Graph Theory, 61(3), pp. 189–206.
• Goto, S., Miyano, E. and Shimizu, R., (2021), Exact values of the connected domination number in grid graphs, Discrete Applied Mathematics, 289, pp. 155–162.
• Mafuta, C. and Mynhardt, C, M., (2023), Connected domination and traceability in graphs, Discrete Mathematics, 346(9), p.113632.
• Liu, G., (2004), Domination in 4-regular graphs, Discrete Mathematics, 275(1–3), pp. 289–296.
• Hurink, J, L. and Nieberg, T., (2008), Approximating minimum independent dominating sets in wireless networks, Information Processing Letters, 109(2), pp. 155–160.
• Ahangar, A, S., Samodivkin, G. and Alikhani, S., (2009), Domination parameters in 4-regular graphs, Utilitas Mathematica, 81, pp. 37–47.
• Harant, J., (2009), A bound on the domination number of bipartite graphs with minimum degree at least 2. Discrete Mathematics, 309(8), pp. 2435–2438.
• Desormeaux, W, J., Haynes, T, W. and Henning, M, A., (2014), Slater-type bounds for the domination number of a tree, Discrete Mathematics, 323, pp. 26–33.
• Pandey, K, K. and Srivastava, J, N., (2018), Domination in subclasses of bipartite graphs, Discrete Applied Mathematics, 234, pp. 123–132.
• BBN Reports, (1981), Butterfly Parallel Processor Overview, Bolt Beranek and Newman Inc., Technical Report No. 6148.
• Leighton, F, T., (1992), Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, San Mateo, CA: Morgan Kaufmann.