An In-depth Analysis of Domination in Graphs: Investigating the Domatic Number, Its Applications, and Computational Challenges

References

[1] Alon, N., Cioaba, S. M., Gilbert, B. D., Koolen, J. H., & McKay, B. D. (2018). Addressing Johnson graphs, complete multipartite graphs, odd cycles and other graphs. arXiv preprint arXiv:1808.04757

[2] Balasubramaniyan, G. (2020). Domination and Domatic Number of a Graph. International Research Journal of Modernization in Engineering Technology and Science, 3(5), 2197-2200

[3] Cardei, M., Thai, M. T., Li, Y., & Wu, W. (2005). Energy-efficient target coverage in wireless sensor networks. IEEE INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 3, 1976-1984

[4] Cockayne, E. J., & Hedetniemi, S. T. (1977). Towards a theory of domination in graphs. Networks, 7(3), 247-261.

[5] Chang, G. J. (1994). The domatic number problem. Discrete Mathematics, 125(1-3), 115-122.

[6] Cardei, M., Thai, M. T., Li, Y., & Wu, W. (2005). Energy-efficient target coverage in wireless sensor networks. IEEE INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 3, 1976-1984. https://doi.org/10.1109/INFCOM.2005.1498477

[7] Chaemchan, A. (2010). The Edge Domination Number of Connected Graphs. Australasian Journal of Combinatorics, 48, 185-189.

[8] Dash, S. P. (2020). Vertex-Domatic, Edge-Domatic and Total Domatic Number of Uniform Hypergraphs. arXiv preprint arXiv:2009.02783. https://arxiv.org/abs/2009.02783

[9] Ene, A., Korula, N., & Vakilian, A. (2013). Connected domatic packings in node-capacitated graphs. arXiv preprint arXiv:1305.4308

[10] Feige, U., Halldórsson, M. M., Kortsarz, G., & Srinivasan, A. (2002). Approximating the domatic number. SIAM Journal on Computing, 32(1), 172-195. https://doi.org/10.1137/S0097539700384047

[11] Francis, P., & Rajendraprasad, D. (2020). On domatic and total domatic numbers of product graphs. arXiv preprint arXiv:2103.10713.

[12] Gao, J., Guibas, L. J., & Nguyen, A. (2012). Maintaining dynamic shortest paths in evolving hypergraphs. Proceedings of the IEEE INFOCOM 2012 Conference, 1441-1449. https://doi.org/10.1109/INFCOM.2012.6195507

[13] Gera, R., Haynes, T. W., Hedetniemi, S. T., & Henning, M. A. (2018). An annotated glossary of graph theory parameters, with conjectures. In Graph Theory: Favorite Conjectures and Open Problems-2 (pp. 177-281). Cham: Springer International Publishing.

[14] Kulli, V. R., & Janakiram, B. (2005). The Minimal Dominating Graph. Graph Theory Notes of New York, 28, 12-15

[15] Pino, T., Choudhury, S., & Al-Turjman, F. (2018). Dominating set algorithms for wireless sensor networks survivability. IEEE Access, 6, 17527-17532.

[16] Riege, T., & Rothe, J. (2005). An exact 2.9416n2.9416^n2.9416n algorithm for the three domatic number problem. Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, 769-780. https://doi.org/10.1007/11538462_16

[17] Riege, T., & Rothe, J. (2006). An improved exact algorithm for the domatic number problem. arXiv preprint arXiv:cs/0603060.

[18] Wang, C., Luo, C., Jia, L., & Zhang, Q. (2015). Domatic partition in homogeneous wireless sensor networks. In Wireless Algorithms, Systems, and Applications (pp. 508-517). Springer. https://doi.org/10.1007/978-3-319-21837-3_50

[19] Vastardis, N., & Yang, K. (2013). Mobile Social Networks: Architectures, Social Properties, and Key Research Challenges. IEEE Communications Surveys & Tutorials, 15(3), 1355-1371

[20] Wadayama, T., Izumi, T., & Ono, H. (2015). Subgraph domatic problem and writing capacity of memory devices with restricted state transitions. arXiv preprint arXiv:1501.04402.

@article{1702139,
      author = {M. S. Patil},
      title = {An In-depth Analysis of Domination in Graphs: Investigating the Domatic Number, Its Applications, and Computational Challenges},
      journal = {Iconic Research And Engineering Journals},
      year = {2020},
      volume = {3},
      number = {10},
      pages = {343-353},
      issn = {2456-8880},
      url = {https://www.irejournals.com/formatedpaper/1702139.pdf},
      abstract = {Graph domination is a central notion of graph theory that refers to a set of vertices such that each vertex in a graph is either part of this set or adjacent to at least one vertex in that set, and the domatic number a measure of how a graph can be partitioned into disjoint dominating sets is a fundamental metric with far-reaching implications across network design, social dynamics modeling, and optimization theory that has mostly concentrated on theoretical foundations, complexity classes, and algorithmic methods for the computation of domatic numbers in different graph classes, such as trees, planar graphs, and bipartite graphs whilst dealing with the NP-completeness of the problem for general graphs, and improving the knowledge of upper and lower bounds through structural properties with key results including exact algorithms for special cases in graph families such as chordal graphs and split graphs, heuristic methods for approximating solutions in dense and sparse graphs, and computational studies relating domatic partitions to real-life applications, like distributed systems where the trade-off between resources allocation and redundancy is crucial, extending to reliable communication networks which require efficient dominating configurations for fault tolerance and connectivity, social network analysis where dominating sets can be used to model influent groups, and finally in wireless sensor networks where the use of domatic partitions improves energy-efficient clustering and fault-tolerant node coverage, all of which keep theoretical challenges ongoing like extending domatic number concepts to weighted graphs, directed graphs, and dynamic or evolving networks showing the interplay existing between combinatorial optimization, graph coloring, and domination-based parameters, whilst recent advancements have also delved into game-theoretic approaches and probabilistic methods to estimate domatic partitions, and current open questions remain in closing the gap between theoretical notions and computational feasibility for large-scale graphs, specifically in hypergraphs and geometric graphs, which emphasizes the urgency of further conceptual and algorithmic advancements to broaden the reach and efficiency of domatic number calculations across emerging interdisciplinary areas that rely on graph-theoretical solutions.},
      keywords = {Domatic Number, Graph Theory, Dominating Sets, Computational Complexity, Network Optimization, Algorithmic Strategies},
      month = {April},
  }