Computational Analysis of Certified Reinforcement Numbers Across Specialized Graph Classes

A certified dominating set D of a graph G is a dominating set in which every vertex in D must have either no neighbors or at least two neighbors in V\D, where V denotes the set of all vertices in G. A certified domination number of G represented by γcer(G) is defined as the smallest size of such a certified dominating set of G. The reinforcement number r(G) is defined to be the cardinality of minimum number of edges F ⊂ E(Gˉ) such that γ(G + F) < γ(G), broadened this parameter to encompass certified domination and we define certified reinforcement number of a graph G, rcer(G) to be the cardinality of the minimum number of edges F ⊂ E(¯G) such that γcer(G + F) < γcer(G) that is minimum number of edges to be added to decrease the certified domination number of G at least by one. In this paper, we characterize the graph G for which rcer(G) = 1 and determine the values of certified reinforcement number for various classes of graphs.