Algorithmic approach, mathematical modelling and network applications of connected certified domination in graphs: A comprehensive review

¹ Department of Mathematics, Dr. D. Y. Patil Institute of Technology, Pimpri, Pune, 411018, Maharashtra, India.
² School of Engineering, Ajeenkya D.Y. Patil University, Lohegaon, Pune, 412105, Maharashtra, India.

Published online: 1 July 2026

Abstract

In this study we have reviewed a very important variant of graph domination theory that is connected certified domination (CCD) and also presents CCD as graph-based model for network optimization. CCD is the minimum set of vertices that dominates all other vertices also satisfies certification condition and induced connected subgraph. Connected certified domination is actually a combination of three very important variant like domination, certification, and connectivity. In this paper we have addresses the algorithmic and computational complexity of the CCD decision problem, confirming its NP-completeness for general graphs and polynomial-time solutions for restricted classes. Also, we have analysed the structural properties of graphs considering CCD, examining extremal graphs and results of the Nordhaus-Gaddum type. The characterization of connected certified domination number for fundamental graph classes, including explicit formulae for paths P_n and cycles C_n and explore its relationships with other classical domination parameters such as domination number and connected domination number we surveyed in this paper. CCD have applications in secure and fault-tolerant network design, this review integrates the key theoretical developments across various side of the field. Also we have given an algorithm, supported by flowchart representation, for computing connected certified domination number which is useful in many network optimization problem. This paper also highlights CCDN as a mathematical modelling tool, CCDN as a combinatorial optimization problem and its application in network. Finally future research direction are also identified.