A set \(D\) of vertices of a graph \(G=(V_G,E_G)\) is a dominating set of \(G\) if every vertex in \(V_G-D\) is adjacent to at least one vertex in \(D\). The domination number of a graph \(G\), denoted by \(\gamma(G)\), is the cardinality of a smallest dominating set of \(G\). A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\), and every vertex in \(D\) has either zero or at least two neighbours in \(V_G-D\). The cardinality of a smallest certified dominating set of \(G\) is called the certified domination number of \(G\), and it is denoted by \(\gamma_{\rm cer}(G)\). A vertex \(v\) of \(G\) is certified critical if \(\gamma_{\rm cer}(G -v) < \gamma_{\rm cer}(G)\), and a graph \(G\) is vertex certified domination critical or \(\gamma_{cer}\)–critical if the removal of any vertex reduces its certified domination number. In this paper, we give examples and properties of certified critical vertices and vertex certified domination critical graphs. As an example of an application of certified critical vertices, we give a constructive characterisation of trees for which the smaller partite set is a minimum certified dominating set.
All graphs discussed here are finite and undirected with no loops and multiple edges. We generally follow the notation and terminology of [11]. For a graph \(G\), \(V_G\) denotes the set of vertices, while \(E_G\) denotes the edge set. The number of vertices in a graph \(G\) is called the order of \(G\), denoted by \(n = |V_G|\). In a connected graph \(G\), the distance \(d_G(u,v)\) from a vertex \(u\) to a vertex \(v\) is the smallest length of a \(u\)–\(v\) path in \(G\). The diameter \(\mathrm{diam}(G)\) of a connected graph \(G\) is the greatest distance between any two vertices of \(G\). For a vertex \(v \in V_G\), the open neighbourhood \(N_G(v)\) of \(v\) is the set of all vertices adjacent to \(v\), and \(N_G[v] = N_G(v) \cup \{v\}\) is the closed neighbourhood of \(v\). The open neighbourhood of a set \(X \subseteq V_G\) is \(N_G(X) = \bigcup_{v \in X} N_G(v)\), while the closed neighbourhood of \(X\) is \(N_G[X] = N_G(X) \cup X\). The set of its leaves (vertices of degree one) is denoted by \(L_G\), the set of support vertices (neighbors of leaves) is denoted by \(S_G\), the subset of weak support vertices adjacent to exactly one leaf is denoted by \(S_G^1\), while the corona of a graph is constructed by adding a unique pendant vertex to each of its original vertices.
Given a graph \(G\), we say that a subset \(D \subseteq V_G\) is a dominating set of \(G\) if every vertex in \(V_G – D\) has a neighbour in \(D\), while \(D\) is \(2\)-dominating if every vertex in \(V_G – D\) has at least two neighbours in \(D\). The domination number of a graph \(G\), denoted by \(\gamma(G)\), is the cardinality of a smallest dominating set of \(G\). A dominating set of \(G\) of minimum cardinality is called a \(\gamma\)-set of \(G\). A subset \(D \subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex belonging to \(D\) has either zero or at least two neighbours in \(V_G – D\). The cardinality of a smallest certified dominating set of \(G\) is called the certified domination number of \(G\), and is denoted by \(\gamma_{{\rm cer}}(G)\). A certified dominating set of \(G\) of minimum cardinality is called a \(\gamma_{{\rm cer}}\)-set of \(G\). For later reference, we recall without proof several further standard variants: a total dominating set requires every vertex to be adjacent to a vertex in the set, and its minimum size is the total domination number \(\gamma_{t}(G)\); a paired dominating set induces a perfect matching, and its minimum size is \(\gamma_{p}(G)\); an independent dominating set is dominating and independent, with minimum size \(\gamma_{i}(G)\); a Roman dominating function \(f\!:V_G\!\to\!\{0,1,2\}\) assigns 2 to at least one neighbour of each vertex with \(f(v)=0\), and the minimum weight \(\sum_{v}f(v)\) is the Roman domination number \(\gamma_{R}(G)\); finally a power dominating set is a set whose iterative forcing process observes all vertices, and the minimum size of such a set is \(\gamma_{P}(G)\). Whenever \(\psi\) denotes any of these parameters, a vertex \(v\) is \(\psi\)-critical if \(\psi(G-v)<\psi(G)\).
Certified domination was introduced by Dettlaff et al. [8] to model certain social network relations. In [21], sufficient conditions were given for the equality of the domination number \(\gamma(G)\) and the certified domination number \(\gamma_{{\rm cer}}(G)\) of a graph \(G\). Moreover, relationships between certified dominating sets and \(2\)-dominating sets were established in [22, 23].
Recently, numerous works have advanced the study of certified domination from structural, algorithmic, and applied perspectives. For instance, Jakkepalli et al. [19] and Raczek and Miotk [25] proved that determining \(\gamma_{{\rm cer}}(G)\) is NP-complete in general (even for various restricted graph classes) and presented efficient algorithms for computing \(\gamma_{{\rm cer}}(G)\) in special cases. In addition, new variants of the concept have been introduced. Hamja [12] defined the certified perfect dominating set, which integrates the perfect domination condition into certified domination. Meanwhile, the connected certified domination number, which requires a dominating set that is both certified and whose induced subgraph is connected, was first investigated in [2] and later characterized for critical cases by Lone and Goswami [1].
Several recent studies have also examined structural properties of \(\gamma_{{\rm cer}}(G)\) and its applications. Pushpam et al. [24] analyzed the stability of the certified domination number under edge addition, identifying families of graphs in which \(\gamma_{{\rm cer}}(G)\) remains invariant when new edges are added. Durai Raj and Kumari [26] investigated \(\gamma_{{\rm cer}}(G)\) in graph products, determining exact values for certain graph constructions. Notably, certified domination has been applied in network design and optimization. Raczek and Miotk [18] utilized \(\gamma_{{\rm cer}}(G)\) to model and optimize fire‑fighting water supply networks, demonstrating the effectiveness of certified dominating sets in meeting resource constraints. The same authors subsequently proposed two heuristic approaches for selecting influential nodes in social networks using certified dominating sets [25], underscoring the practical relevance of \(\gamma_{{\rm cer}}(G)\) in real-world scenarios.
Brigham, Chinn, and Dutton [5] began the study of vertex domination-critical graphs by investigating how the domination number decreases upon the removal of any single vertex. Further properties of these graphs were explored in [7, 10, 9, 31, 30]. However, a complete characterisation of domination-critical graphs is still unknown. Various types of critical graphs have been examined with respect to domination parameters (considering vertex or edge removal, as well as vertex or edge addition), including paired-domination-critical, double-domination-critical, and isolate-domination-critical cases in [17, 27, 28]. In this paper, we are interested in studying the effect that graph modifications have on the certified domination number. More precisely, we first investigate graphs for which the certified domination number decreases following the removal of any vertex. We call such a vertex certified critical. (In [8], the effect on the certified domination number of adding a vertex or an edge was previously examined.) As an example of the utility of certified critical vertices, we provide a sufficient condition in bipartite graphs under which the smaller partite set is a minimum certified dominating set. For trees, we give a constructive, complete characterisation of those graphs whose smaller partite set is a \(\gamma_{{\rm cer}}\)-set. Finally, we provide a characterisation of \(2\)-vertex certified domination-critical graphs using the terminology of the graph factorisation problem.
An influence vertex of a domination parameter \(\psi(G)\) is a vertex whose removal necessitates a qualitative adjustment in the optimal size of an existing dominating set under such a model. The identification of these vertices reveals where a network is structurally vulnerable and how its resource needs are affected by a localized disruption.
\(\textbf{Standard domination }(\gamma)\). In the classical environment, a \(\gamma\)–critical vertex reveals hidden redundancy if \(\gamma(G\!-\!v)<\gamma(G)\) or identifies a point of unique failure when \(\gamma(G\!-\!v)>\gamma(G)\) [5]. Freight‑logistics hubs whose loss raises \(\gamma\) mark warehouses whose protection avoids costly re‑routing.
\(\textbf{Total domination} (\gamma_{t})\). As every vertex must be backed up by a neighbour, \(\gamma_{t}\)–critical vertices highlight sensitivity in local backup systems such as peer‑to‑peer monitors or redundant servers [6].
\(\textbf{Paired domination}\) \((\gamma_{p})\). Here dominating vertices appear in mutually‑aiding pairs. A \(\gamma_{p}\)–critical vertex is on a bottleneck matching edge: its removal destroys a minimal pair and compels the network to hire an entire extra pair of resources [14]. Guard patrols or twin‑server clusters are natural analogies.
\(\textbf{Independent domination ($\gamma_{i}$).}\) While dominating vertex do not have to be non-adjacent, \(\gamma_{i}\)–critical nodes provide the interference versus coverage trade-off. For wireless sensor grids a critical access point can result in extra nodes being deployed (if \(\gamma_{i}\) is increased) or allow a sparse, interference-free network (if \(\gamma_{i}\) is reduced) [3].
Power domination \((\gamma_{P})\). A power‑critical bus in an electric network is one whose loss requires extra Phasor Measurement Units in order to restore full observability [15]. The grid operators therefore view such buses as topological “linchpins” for state‑estimation redundancy.
Let a regional distribution network be represented by a bipartite graph \(G=((A,B);E_G)\), with the set \(A\) representing possible distribution centers and the set \(B\) representing retail outlets.
A certified dominating set \(D_{{\rm cer}} \subseteq A\) is related to the opened centres: every outlet in \(B\) is within reach of at least one opened hub, and every hub serves either no outlet (unused back‑up location) or at least two outlets (economies of scale). This “\(0\) or \(\ge2\)” requirement precisely models a common cost constraint: it is uneconomical to operate a centre to serve a single outlet, but demanding two centres per outlet (as in double domination) is too costly. Let \(G\) be the star \(K_{1,3}\) with central vertex \(v\in A\) adjacent to three outlets \(b_{1},b_{2},b_{3}\in B\). As \(v\) dominates every outlet and satisfies the certified condition (\(|N_G(v)\cap B|=3\ge2\)), we obtain \(\gamma_{\mathrm{cer}}(G)=1\) with \(D_{{\rm cer}}=\{v\}\). Vertex \(v\) is therefore certified‑domination‑critical: removing it isolates the outlets, and each outlet becomes a micro‑hub in itself, yielding the certified dominating set \(D_{{\rm cer}}'=\{b_{1},b_{2},b_{3}\}\) and raising the parameter to \(\gamma_{\mathrm{cer}}(G-v)=3\). In terms of operations, the removal of \(v\) triples the number of active facilities, ballooning fixed costs and complicating inventory flows. Therefore certified domination-critical vertices identify the hubs whose presence sustains the optimal balance between efficiency (minimal centres) and redundancy (no single-client centres). Finding them in larger supply graphs signals precisely where to maximize contingency stock or redundant routing capacity, providing practical guidance for resilient cost-effective logistics planning.
Let \(G = (V_G,E_G)\) be a graph. A vertex \(v\) is certified critical if \(\gamma_{\rm cer}(G – v) < \gamma_{\rm cer}(G)\). Additionally, \(G\) is vertex certified domination critical, or \(\gamma_{\rm cer}\)–critical, if each vertex of \(G\) is certified critical.
In [8], it was observed that, for a graph \(G\) of order \(n\), \(1 \leq \gamma_{\rm cer}(G) \leq n\), it is obvious that, if \(\gamma_{{\rm cer}}(G) = 1\), then \(G\) is vertex certified domination critical graph if and only if \(G = K_1\). The next question is to characterise a vertex certified domination critical graph \(G\), for which \(\gamma_{\rm cer}(G) = n\). This gives rise to the following Observation.
Observation 3.1. Let \(G\) be a graph of order \(n\). If \(\gamma_{\rm cer}(G) = n\), then \(G\) is a vertex certified domination critical graph.
Proof. Suppose that \(\gamma_{\rm cer}(G) = n\) and \(G\) is not a \(\gamma_{\rm cer}\)-critical graph. Then there exists a vertex \(v\) of \(G\) such that \(\gamma_{\rm cer}(G – v) \geq \gamma_{\rm cer}(G) = n\). Hence, \(v\) must belong to every \(\gamma_{\rm cer}\)-set of \(G\), which contradicts the fact that \(\gamma_{{\rm cer}}(G – v) = n\). ◻
In [8], it was demonstrated that, for a graph \(G\) of order \(n\), \(\gamma_{\rm cer}(G) = n\) if and only if \(G\) is the complement of a complete graph, the corona of a graph, or the union of both. Taking into account the above result and Observation 3.1, we have the following Corollary.
Corollary 3.2. Let \(G\) be a graph of order \(n\). If \(G\) is the complement of a complete graph, the corona of a graph, or the union of both, then \(G\) is a vertex certified domination critical graph.
Figure 1 presents graphs \(G\) and \(H\), which are \(\gamma_{{\rm cer}}\)-critical and not \(\gamma_{{\rm cer}}\)-critical, respectively. Notice that the graph \(G\) is the corona, which means that the vertices of \(G\) must belong to the minimum certified dominating set. It follows from Corollary 3.2 that \(G\) is a vertex certified domination critical graph. For a graph \(H\), the unique minimum certified dominating set is \(\{u_1,u_3\}\), and it is easy to check that, for every vertex of \(H\), the certified domination number does not decrease.
Now, we focus on characterising the most common classes of graphs, namely vertex certified domination critical graphs. In [8], it was observed that, for a complete graph \(K_n\) of order \(n\), we have \(\gamma_{\rm cer}(K_n)= 1\) if \(n\not=2\) or \(\gamma_{{\rm cer}}(K_n) = 2\) if \(n=2\). For a cycle \(C_n\) of order \(n\), the certified domination number \(\gamma_{\rm cer}(C_n)= \lceil n/3\rceil\) if \(n\geq 3\). For a path \(P_n\) of order \(n\), we have \(\gamma_{{\rm cer}}(P_1) = 1\), \(\gamma_{{\rm cer}}(P_2) = 2\), \(\gamma_{{\rm cer}}(P_4) = 4\), or \(\gamma_{{\rm cer}} (P_n) = \lceil n/3 \rceil\) if \(n = 3\) or \(n \geq 5\). Additionally, it was also proven that for a graph \(G\), every support vertex must belong to every \(\gamma_{{\rm cer}}\)-set of \(G\). In the observations given below, a characterisation is presented of vertex certified domination critical complete graphs and cycles.
Observation 3.3. Let \(G\) be a complete graph of order \(n\). Then \(G\) is a vertex certified domination critical graph if and only if \(n \in \{1,2\}\).
Proof. Suppose that the complete graph \(G\) is \(\gamma_{\rm cer}\)-critical, and let \(n \geq 3\). Then \(\gamma_{\rm cer}(G) = 1\). Additionally, since the graph \(G' = G – v\) for some vertex \(v\) of \(G\), is a complete graph of order \(n-1\), we have the contradiction \(\gamma_{\rm cer}(G') \geq \gamma_{\rm cer}(G)\).
On the other hand, if \(n = 1\) and \(v\) is a vertex of \(G\), then \(\gamma_{\rm cer}(G) = 1\) and \(\gamma_{\rm cer}(G') = 0\), where \(G' = G – v\). If \(n = 2\), then \(G\) is a corona graph of \(K_1\), and from Corollary 3.2, it follows that \(G\) is a \(\gamma_{\rm cer}\)-critical graph. ◻
Observation 3.4. Let \(G\) be a cycle of order \(n\), where \(n \geq 3\). Then \(G\) is a vertex certified domination critical graph if and only if \(n = 3k + 1\) for \(k \in \mathbb{N}^+\).
Proof. Let \(G\) be a cycle of order \(n\), where \(n \geq 3\) and \(G\) is \(\gamma_{\rm cer}\)-critical. Let \(n \neq 3k + 1\) for \(k \in \mathbb{N}^+\). We need to consider the following two cases. If \(n = 3k\), then \(\gamma_{\rm cer}(G) = k\). Let \(v\) be a vertex of \(G\). If \(k = 1\), then \(G' = G – v = K_2\) and \(\gamma_{\rm cer}(G') = 2 > \gamma_{\rm cer}(G)\), which is a contradiction, namely that \(G\) is \(\gamma_{\rm cer}\)-critical. Now, assume that \(k > 1\). Hence, the graph \(G' = G – v\) is the path of order \(3k – 1\) and \(\gamma_{\rm cer}(G') = k = \gamma_{\rm cer}(G)\), which is another contradiction, namely that \(G\) is a \(\gamma_{\rm cer}\)-critical graph. Now, suppose that \(n = 3k + 2\). Then \(\gamma_{\rm cer}(G) = k+1\). Let \(v\) be a vertex of \(G\). Then the graph \(G' = G – v\) is the path of order \(3k + 1\), and we have \(\gamma_{\rm cer}(G') = k + 1\). This is also a contradiction, namely that \(G\) is \(\gamma_{\rm cer}\)-critical graph.
Suppose that \(G\) is a cycle of order \(3k + 1\) for \(k \in \mathbb{N}^+\). Suppose that \(G\) is not a \(\gamma_{\rm cer}\)-critical graph. Then there exists a vertex \(v\) of \(G\) such that \(\gamma_{\rm cer}(G – v) \geq \gamma_{\rm cer}(G)\). The certified domination number of \(G\) is equal to \(k + 1\), while \(\gamma_{\rm cer}(G – v) = k\). This contradicts the fact that \(G\) is not a \(\gamma_{\rm cer}\)-critical graph, thereby completing the proof. ◻
The next results show that there does not exist a certified critical strong support vertex. We start with the following observation.
Observation 3.5. Let \(G=(V_G,E_G)\) be a graph. If there exists a strong support vertex \(s\) in \(G\), then there exists a vertex \(u \in V_G\) such that \(\gamma_{\rm cer} (G – u) \geq \gamma_{\rm cer}(G)\).
Proof. Let \(s\) be a strong support vertex of \(G\) and let \(L = N_G(s) \cap L_G\) be a set of leaves of \(s\). Now, let \(u \in L\). We have \(\gamma_{\rm cer}(G – u) \geq \gamma_{\rm cer}(G)\), since every support vertex belongs to every minimum certified dominating set. ◻
Based the above observation, we obtain the following Corollary.
Corollary 3.6. If \(G\) is a vertex certified domination critical graph, then there is no strong support vertex in the graph \(G\).
Our next goal is to characterize the certified critical leaves and support vertices using the private neighbourhood notation and shadowed vertex definition. Recall that the private neighbourhood \(pn[v, S]\) of \(v \in S\) is defined by \(pn[v, S] = N[v] – N[S – \{v\}]\) for \(S \subseteq V_G\) of the graph \(G\). Equivalently, \(pn[v, S] = \{u \in V \colon N[u] \cap S = \{v\}\}\). Each vertex in \(pn[v, S]\) is called a private neighbour of \(v\). A vertex \(v\) of a graph \(G\) is said to be shadowed with respect to a certified dominating set \(D_{{\rm cer}}\) if \(N_G[v]\subseteq D_{{\rm cer}}\), while \(v\) is half-shadowed if \(|N_G(v) \cap D_{{\rm cer}}| = 1\). Consider the graph \(G\) from Figure 1, in which all vertices belong to the minimum certified dominating set \(D_{{\rm cer}}\). Thus, every vertex \(v\) of \(G\) is shadowed, and it is easy to check that \(pn[v,D_{{\rm cer}}] = \emptyset\). For the graph \(H\) in Figure 1, the unique \(\gamma_{{\rm cer}}\)-set \(D_{{\rm cer}} = \{u_1,u_3\}\), and we have \(pn[u_1,D_{{\rm cer}} ] = \{u_0,u_1,u_5,u_6\}\) and \(pn[u_3, D_{{\rm cer}}] = \{u_3,u_4\}\).
The next result is a characterisation of shadowed vertices, taking into account the private neighbourhood notation.
Lemma 3.7. Let \(G\) be a graph. Then a vertex \(v\) is shadowed if and only if \(pn[v,D_{\rm cer}] = \emptyset\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\).
Proof. Suppose that \(v\) is shadowed vertex. Since \(N_G[v] \subseteq D_{\rm cer}\) for some \(\gamma_{\rm cer}\)-set of \(G\), it is clear that \(pn[v,D_{\rm cer}] = \emptyset\).
Now, let \(pn[v,D_{\rm cer}] = \emptyset\) for some \(\gamma_{\rm cer}\)-set of \(G\) containing \(v\). Suppose to the contrary that \(v\) is not shadowed. Since \(pn[v,D_{\rm cer}] = \emptyset\) and \(v\) is not shadowed, we conclude that \(v\) is not a support or a leaf (otherwise \(pn[v,D_{\rm cer}] \neq \emptyset\) or \(v\) is a half-shadowed vertex, which is impossible in \(D_{\rm cer}\)). Therefore, the set \(D'_{\rm cer} = D_{\rm cer} – \{v\}\) would be a smaller certified dominating set, which yields a contradiction. This completes the proof. ◻
Lemma 3.8. Let \(G\) be a graph. Then for a vertex \(v\) and \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\), we have \(pn[v,D_{\rm cer}] = \emptyset\) if and only if \(v\) is shadowed and \(v \in L_G \cup S^1_G\).
Proof. Let \(pn[v,D_{\rm cer}] = \emptyset\) for some \(\gamma_{\rm cer}\)-set \(D_{{\rm cer}}\) of \(G\) containing \(v\). By Lemma 3.7, it follows that \(v\) is a shadowed vertex. Now, it is remains to be proven that \(v\) is a leaf or weak support vertex. On the contrary, suppose that this is not true. Since \(pn[v,D_{\rm cer}] = \emptyset\), it follows that \(v\) is not a strong support vertex and \(d_G(v) \geq 2\). Based on the assumption that \(v\) is shadowed, then \(N_G(v) \subseteq D_{\rm cer}\), and the set \(D'_{\rm cer} = D_{\rm cer} – \{v\}\) would be a smaller certified dominating set, thereby yielding a contradiction.
Now, assume that \(v\) is shadowed and \(v\) is a weak support or a leaf. From Lemma 3.7, we have \(pn[v,D_{\rm cer}] = \emptyset\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\). ◻
The next results provide the characterisation of certified critical support vertices and leaves.
Lemma 3.9. Let \(G\) be a graph. If \(v\) is shadowed vertex of \(G\), then \(v\) is certified critical.
Proof. Let \(v\) be a shadowed vertex for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\). From Lemma 3.7, it follows that \(pn[v,D_{\rm cer}] = \emptyset\). Since \(v\) does not contain a private neighbour in \(D_{\rm cer}\), then the set \(D'_{\rm cer} = D_{\rm cer} – \{v\}\) is certified dominating set in \(G – v\). Hence, we obtain \(\gamma_{\rm cer}(G -v) < \gamma_{\rm cer}(G)\), and therefore \(v\) is certified critical. ◻
Lemma 3.10. Let \(G\) be a graph. If for a weak support \(s\) and its leaf \(l\) it follows that \(pn[s,D_{\rm cer}] = \{l\}\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(s\), then \(l\) is certified critical.
Proof. Suppose that \(pn[s,D_{\rm cer}] = \{l\}\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(s\). Since \(l\) is the only private neighbour of \(s\) and for every non-leaf neighbour \(u\) of \(s\), \(N_G(u) \cap (D_{{\rm cer}} – \{s\}) \neq \emptyset\), then the set \(D'_{\rm cer} = D_{\rm cer} – \{s\}\) is a certified dominating set in \(G -l\). Hence, \(\gamma_{\rm cer}(G – l) < \gamma_{\rm cer}(G)\), and therefore \(l\) is certified critical. ◻
Lemma 3.11. Let \(G\) be a graph. A support vertex \(s\) is certified critical if and only if \(s\) is a shadowed vertex.
Proof. Let \(s\) be certified critical vertex. It follows from Corollary 3.6 that \(s\) is a weak support. Suppose to the contrary that \(s\) is not a shadowed vertex, that is \(N_G[s] \subsetneq D_{\rm cer}\). Let \(l\) be a leaf of \(s\). It follows that \(l \notin D_{\rm cer}\), and we have \(\gamma_{\rm cer}(G – s) \geq \gamma_{\rm cer}(G)\) since \(l\) is an isolated vertex in \(G-s\) and \(l\) belongs to every \(\gamma_{\rm cer}\)-set of \(G – s\). This contradicts our assumption that \(s\) is certified critical vertex.
Now, assume that \(s\) is a shadowed vertex. From Lemma 3.9, we conclude that \(s\) is certified critical, which completes the proof. ◻
In [9], it was demonstrated that a vertex \(v\) is critical if and only if \(pn[v,D] = \{v\}\) for some \(\gamma\)-set \(D\) of \(G\) containing \(v\). Using a similar technique, we have the following Lemma.
Lemma 3.12. Let \(G\) be a graph. If \(pn[v,D_{\rm cer}] = \{v\}\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\), then \(v\) is certified critical.
Proof. The proof is adapted from [9]. Assume that \(pn[v,D_{\rm cer}] = \{v\}\) for some \(\gamma_{\rm cer}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\). Since \(N_G(v) \cap D_{\rm cer} = \emptyset\), the set \(D_{\rm cer} – \{v\}\) is certified dominating set in \(G – v\). Consequently, \(v\) is certified critical. ◻
Now, we are ready to give a complete characterisation of vertex certified domination critical graphs. We start from the graphs without leaves and isolated vertices.
Theorem 3.13. Let \(G\) be a graph with a minimum degree of at least two. Then \(G\) is vertex certified domination critical graph if and only if for each vertex \(v\) of \(G\), \(pn[v,D_{{\rm cer}}] = \{v\}\) for some \(\gamma_{{\rm cer}}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\).
Proof. Let \(G\) be a \(\gamma_{{\rm cer}}\)-critical graph. Hence, every vertex of \(G\) is certified critical. Suppose to the contrary that there exists a vertex \(v\) such that \(pn[v,D_{{\rm cer}}] \neq \{v\}\) for all \(\gamma_{{\rm cer}}\)-sets \(D_{{\rm cer}}\) of \(G\) containing \(v\). Hence, there exists at least one private neighbour distinct of \(v\). Therefore, the set \(D_{{\rm cer}} – \{v\}\) would not be a certified dominating set of \(G – v\), thereby yielding a contradiction.
Now, suppose that, for each vertex \(v\) of \(G\), \(pn[v,D_{\rm cer}] = \{v\}\) for some \(\gamma_{{\rm cer}}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\). It follows from Lemma 3.12 that \(v\) is certified critical. Therefore, \(G\) is a vertex certified domination critical graph. ◻
Considering Theorem 3.13, the following result can be obtained.
Theorem 3.14. Let \(G\) be a graph. Then \(G\) is a vertex certified domination critical graph if and only if for each vertex \(v\) of \(G\), \(pn[v,D_{{\rm cer}}] = \{v\}\) or \(pn[v,D_{{\rm cer}}] = \emptyset\) for some \(\gamma_{{\rm cer}}\)-set \(D_{{\rm cer}}\) of \(G\) containing \(v\).
Proof. Suppose that \(G\) is a \(\gamma_{{\rm cer}}\)-critical graph. Hence, every vertex \(v\) of \(G\) is certified critical. Conversely, suppose that there exists a vertex \(v\) such that \(pn[v,D_{{\rm cer}}] \neq \emptyset\) and \(pn[v,D_{{\rm cer}}] \neq \{v\}\) for all \(\gamma_{{\rm cer}}\)-set \(D_{{\rm cer}}\) of \(G\) containing \(v\). Hence, \(v\) is not a leaf (otherwise \(v\) would be a shadowed vertex) or an isolated vertex. We need to consider the following two cases. If \(v\) is support, then \(v\) is not shadowed, and it follows from Lemma 3.11 that a contradiction arises with the fact that \(G\) is \(\gamma_{{\rm cer}}\)-critical. Now, we may assume that \(G\) is a graph with a minimum degree of at least two. Therefore, \(v\) is not certified critical by Theorem 3.13. Hence, \(G\) is not a \(\gamma_{{\rm cer}}\)-critical graph, yielding a contradiction with the initial supposition.
Now, suppose that, for every vertex \(v\) of \(G\), \(pn[v,D_{{\rm cer}}] = \emptyset\) or \(pn[v,D_{{\rm cer}}] = \{v\}\) for some \(\gamma_{{\rm cer}}\)-set of \(G\) containing \(v\). Then, it follows from Lemmas 3.9 and 3.12 that \(v\) is certified critical. Therefore, \(G\) is a vertex certified domination critical graph. ◻
As a consequence of Theorem 3.13 and 3.14, the following corollaries and related results can be identified.
Corollary 3.15. Let \(G\) be a connected graph with at least one leaf. Then \(G\) is a vertex certified domination critical graph if and only if \(G\) is a corona of some graph \(G'\).
Proof. Let \(G\) be a \(\gamma_{{\rm cer}}\)-critical graph. Hence, according to Theorem 3.14, it follows that, for every vertex \(v\) of \(G\), \(pn[v,D_{{\rm cer}}] = \emptyset\) or \(pn[v,D_{{\rm cer}}] = \{v\}\) for some \(\gamma_{{\rm cer}}\)-set \(D_{\rm cer}\) of \(G\) containing \(v\). From Observation 3.5, it is reasonable to conclude that \(G\) does not contain strong supports. Hence, every support vertex is shadowed. Suppose to the contrary that \(G\) is not a corona of some graph \(G'\). Then, there exists a weak support \(s\) such that \(N_G(s) – (L_G \cup S_G) \neq \emptyset\). Let \(u \in N_G(s) – (L_G \cup S_G)\). Thus, since \(s\) is shadowed, \(u\) must belong to some \(\gamma_{{\rm cer}}\)-set \(D_{{\rm cer}}\) of \(G\). On the other hand, we have \(pn[u,D_{{\rm cer}}] \neq \{u\}\), and it follows from Theorem 3.14 that \(u\) is not certified critical. Therefore, \(G\) is not a \(\gamma_{{\rm cer}}\)-critical graph, which yields a contradiction.
Assume that \(G\) is a corona of some graph \(G'\). Then it follows from Observation 3.1 that \(G\) is a \(\gamma_{{\rm cer}}\)-critical graph. This completes the proof. ◻
Corollary 3.16. A tree \(T\) is a vertex certified domination critical graph if and only if \(T\) is a corona of some tree \(T'\).
Corollary 3.17. Let \(G\) be a path of order \(n\). Then \(G\) is a vertex certified domination critical graph if and only if \(n \in \{1,2,4\}\).
Corollary 3.18. Let \(G\) be a graph of with a minimum degree of at least two. Then \(G\) is a vertex certified domination critical graph if and only if \(G\) is a domination critical graph.
In this section, an application of the definition of certified critical vertices is given. We give a complete characterisation of bipartite graphs \(G = ((A,B); E_G)\) for which the smaller partite set \(A\) is a minimum certified dominating set. Similar research related to the domination number was undertaken by [13, 20, 4], while [22] gave a partial characterisation of these graphs related to the domination number and \(2\)-dominating sets.
We start with the following Lemma, which are proven in [22].
Lemma 4.1. Let \(G = ((A,B);E_G)\) be a connected bipartite graph with \(1 \leq |A| \leq |B|\). If the set \(A\) is the minimal certified dominating set, then \(A\) does not contain a shadowed vertex.
Proof. Assume that the set \(A\) is a minimal certified dominating set. On the contrary, suppose that there exists a shadowed vertex \(u\) in \(A\). From Lemma 3.8, \(u\) is a leaf or weak support, and \(N_G(u) \subseteq B\) must belong to the minimal certified dominating set. This contradicts the fact that \(A\) is a minimal certified dominating set. ◻
As a consequence of the above Lemma, we have the following Corollary.
Corollary 4.2. Let \(G = ((A,B);E_G)\) be a connected bipartite graph with \(1 \leq |A| \leq |B|\). If the set \(A\) is a \(\gamma_{{\rm cer}}\)-set of \(G\), then \(A\) does not contain shadowed vertices, and hence \(S_G \subseteq A\).
Now, we give a sufficient condition of bipartite graphs \(G = ((A,B); E_G)\) for which \(\gamma_{{\rm cer}}(G) = |A|\), where \(1 \leq |A| \leq |B|\).
Theorem 4.3. Let \(G = ((A,B); E_G)\) be a connected bipartite graph with \(1 \leq |A| \leq |B|\). If the set \(A\) is a \(\gamma_{{\rm cer}}\)-set of \(G\), then the following conditions hold:
\((a)\) Every support vertex belongs to the set \(A\);
\((b)\) Every non-support vertex of the set \(A\) is certified critical.
Proof. Assume that the set \(A\) is a \(\gamma_{{\rm cer}}\)-set of \(G\). The condition \((a)\) follows from Corollary 4.2. Suppose to the contrary that there exists a non-support vertex \(v\) of \(A\), which is not certified critical. Then \(|A| – 1 = \gamma_{{\rm cer}}(G – v) \geq \gamma_{{\rm cer}}(G) = |A|\), which is impossible. This proves condition \((b)\). ◻
Let \(\mathcal{T}_{max}\) denote the set of trees for which the smaller partite set \(A\) is a minimum certified dominating set. We now provide a constructive characterisation of the trees belonging to the set \(\mathcal{T}_{max}\). Similar constructive characterisation of trees for different domination parameters or properties have been presented in other studies, including [16, 20, 29] . Our characterisation is based on two simple operations, and it is similar to the result obtained in [20].
Let \(\mathcal{T}\) be the family of trees \(T\) that can be obtained from a sequence of trees \(T_0,\ldots,T_k\), where \(k \geq 0\), \(T_0 = S_{1,n}\) \((n \geq 2)\) and \(T = T_k\). In addition, if \(k \geq 1\), then for each \(i=1,\ldots,k\), the tree \(T_i\) can be obtained from the tree \(T_{i-1}\) with the bipartition \((A',B')\), where \(|A'| \leq |B'|\). This relies on one of the following two operations: firstly, \(\mathcal{O}_1\); and secondly, \(\mathcal{O}_2\). These operations are defined and illustrated in Figure 2.
\(\mathcal{O}_1\) Add a new vertex \(b\) to \(T'\) and join \(b\) to an \(A'\)-vertex \(a'\) of \(T'\);
\(\mathcal{O}_2\) Add two new vertices \(a\) and \(b\) to \(T'\) and join \(a\) to \(b\) to \(B'\)-vertex \(b'\) of \(T'\), which is not certified critical in \(T'\).
Each of the vertices \(a'\) in the above defined operation \(\mathcal{O}_1\) and \(b'\) in the operation \(\mathcal{O}_2\) are denoted the attachers of \(T'\). We shall prove that the trees in \(\mathcal{T}\) are precisely the trees belonging to the family \(\mathcal{T}_{max}\). Our first aim is to show that each tree in \(\mathcal{T}\) belongs to the family \(\mathcal{T}_{max}\). For this purpose, we prove the following Lemma.
Lemma 4.4. If \(T \in \mathcal{T}\), then \(T \in \mathcal{T}_{max}\).
Proof. Let \(T_0,T_1,T_2,\ldots\) be a sequence of trees, where \(T_0 = S_{1,k} (k \geq 2)\) and every \(T_n\) can be obtained from the tree \(T_{n-1}\) by one of the operations \(\mathcal{O}_1\) and \(\mathcal{O}_2\). By induction on \(n\), we shall prove that \(T_n \in \mathcal{T}_{max}\) for every \(n \in \mathbb{N}\). If \(n = 0\), then \(T_0 = S_{1,k}\) \((k \geq 2)\) and \(T_0 \in \mathcal{T}_{max}\) (as \(\gamma_{{\rm cer}}(S_{1,k}) = 1 = |A|)\). Suppose that \(n \geq 1\) and \(T_{n-1} = ((A',B'), E_{T_{n-1}})\) is a tree, where \((A',B')\) is a bipartition of \(T_{n-1}\) for which \(|A'| \leq |B'|\), and the set \(A'\) is a \(\gamma_{{\rm cer}}\)-set of \(T_{n-1}\). We consider two cases, depending on which operation is used to construct the tree \(T = T_n\) from \(T' = T_{n-1}\).
Case 1. \(T\) is obtained from \(T'\) by operation \(\mathcal{O}_1\). In this case, \((A',B' \cup \{b\})\) is the bipartition of \(T\) and \(|A'| < |B \cup \{b\}|\). Now, since \(A'\) is \(\gamma_{{\rm cer}}\)-set of \(T'\) and the attacher \(a'\) is support vertex, it follows that the set \(A'\) is a \(\gamma_{{\rm cer}}\)-set of \(T\). This proves that \(\mathcal{T} \in \mathcal{T}_{max}\).
Case 2. \(T\) is obtained from \(T'\) by operation \(\mathcal{O}_2\). In this case, \((A' \cup \{a\}, B' \cup \{b\})\) is the bipartition of \(T\) and \(|A' \cup \{a\}| \leq |B' \cup \{b\}|\). Since \(a\) is support vertex, we have \(\gamma_{{\rm cer}}(T) \leq |A' \cup \{a\}| \leq |A'| + 1\). We claim that the set \(A' \cup \{a\}\) is a \(\gamma_{{\rm cer}}\)-set of \(T\). Since \(a\) is a support vertex and \(a\) must belong to every \(\gamma_{{\rm cer}}\)-set of \(T\), then it remains to be proven that \(\gamma_{{\rm cer}}(T) \geq |A' + 1|\). Let \(D_{{\rm cer}}\) be a \(\gamma_{{\rm cer}}\)-set of \(T\). Then \(\gamma_{{\rm cer}}(T) = |D_{{\rm cer}}| \leq |A'| = \gamma_{{\rm cer}}(T')\). Since \(a\) is support vertex, then \(a \in D_{{\rm cer}}\). Now, the attacher \(b'\) is dominated only by \(a\) (otherwise \(D_{{\rm cer}}- \{a\}\) would be a certified dominating set of \(T'\), and we would have \(\gamma_{{\rm cer}}(T') \leq |D_{{\rm cer}} -\{a\} | < |A'| = \gamma_{{\rm cer}}(T')\), yielding a contradiction). Then \(D_{{\rm cer}} – \{a\}\) is certified dominating set of \(T' – b'\). Consequently, \(\gamma_{{\rm cer}}(T' – b') \leq |D_{{\rm cer}} – \{a\}| < |A'|\), which contradicts the fact that \(b'\) is not a certified critical vertex in \(T'\), that is \(\gamma_{{\rm cer}}(T' – b') \geq \gamma_{{\rm cer}}(T')\) for the attacher \(b'\) in operation \(\mathcal{O}_2\). This proves that \(\mathcal{T} \in \mathcal{T}_{max}\), completing the proof. ◻
We are now ready to provide a constructive characterisation of the trees belonging to the family \(\mathcal{T}_{max}\).
Theorem 4.5. \(\mathcal{T} = \mathcal{T}_{max}\).
Proof. It follows from Lemma 4.4 that \(\mathcal{T} \subseteq \mathcal{T}_{max}\). Conversely, suppose \(T\) is a tree belonging to the family \(\mathcal{T}_{max}\). Let \((A,B)\) be a bipartition of \(T\), where \(1 \leq |A| \leq |B|\). By induction on the order of \(T\), we shall prove that, if the set \(A\) is a \(\gamma_{{\rm cer}}\)-set of \(T\), then \(T\) belongs to \(\mathcal{T}\), that is \(T\) can be obtained from \(S_{1,k}\) \((k \geq 2)\) (which belongs to \(\mathcal{T}\) and \(\mathcal{T}_{max}\)) by repeated applications of the operations \(\mathcal{O}_1\) and \(\mathcal{O}_2\). Since a star \(S_{1,k}\) \((k \geq 2)\) belongs to \(\mathcal{T}\) and \(\mathcal{T}_{max}\), we may assume that \(diam(T) \geq 3\). By Observation 3.2 and Theorem 4.3, we may assume that \(|A| < |B|\) and \(|A \cap L_T| = \emptyset\). Let \((x_0,x_1,\ldots,x_d)\) be the longest path in \(T\). Since \(x_0\) and \(x_d\) are leaves in \(T\) and \(d = diam(T) \geq 3\), it is necessarily the case that \(x_0 \in B, \ x_1 \in A,\ldots,x_d \in B\), and therefore \(d \geq 4\). If \(d_T(x_1) > 2\), then \((A,B – \{x_0\})\) is a bipartition of the subtree \(T' = T – x_0\) of \(T\), and it is clear that the set \(A\) is a \(\gamma_{{\rm cer}}\)-set of \(T'\). Thus, \(T' \in \mathcal{T}_{max}\) and the inductive hypothesis imply that \(T' \in \mathcal{T}\). At this point, the tree \(T\) can be rebuilt from \(T'\) by applying the operation \(\mathcal{O}_1\) with the attacher \(x_1\). If \(d_T(x_1) = 2\), then \((A – \{x_1\}, B – \{x_0\})\) is a bipartition of the subtree \(T' = T – \{x_0,x_1\}\) of \(T\) and \(|A – \{x_1\}| < |B – \{x_0\}|\). It is clear that the set \(A – \{x_1\}\) is a \(\gamma_{{\rm cer}}\)-set of \(T'\). Thus \(T' \in \mathcal{T}_{max}\) and the inductive hypothesis imply that \(T' \in \mathcal{T}\). Now, it remains to be proven that \(x_2\) is not a certified critical vertex in \(T'\). Suppose that this is not true, namely that \(x_2\) is a certified critical vertex in \(T'\). Then \(\gamma_{{\rm cer}}(T' – \{x_2\}) \leq \gamma_{{\rm cer}}(T') – 1 \leq |A| – 2\). But now, if \(D_{{\rm cer}}\) is a \(\gamma_{{\rm cer}}\)-set of \(T' – \{x_2\}\), then \(D_{{\rm cer}} \cup \{x_1\}\) is a certified dominating set of \(T\) and \(|A| = \gamma_{{\rm cer}}(T) \leq |D_{{\rm cer}} \cup \{x_1\}| \leq |A| – 1 < \gamma_{{\rm cer}}(T)\), which yields a contradiction. Consequently, since \(x_2\) is not a certified critical vertex in \(T'\), the tree \(T\) can be rebuilt from \(T'\) by applying the operation \(\mathcal{O}_2\) with the attacher \(x_2\). This completes the proof. ◻
Let \(k \in \mathbb{N}^+\). A graph \(G\) is denoted as a \(k\)-vertex certified domination critical graph if it is vertex certified critical and \(\gamma_{\rm cer}(G) = k\). Formally, \(\gamma_{\rm cer}(G) = k\) and for each vertex \(v\) of \(G\), \(\gamma_{\rm cer}(G – v) \leq k – 1\). This definition indicates that \(1\)-vertex certified domination critical graphs are the only complete graphs of order one. Now, we focus on the problem of characterising \(2\)-vertex certified domination critical graphs. To present this characterisation, we introduce some additional terms.
A set of edges in a graph \(G\) is independent if no two edges in the set are adjacent in \(G\). The edges in an independent set of edges of \(G\) are called a matching in \(G\). If \(M\) is a matching in a graph \(G\) with the property that every vertex of \(G\) is incident with an edge of \(M\), then \(M\) is a perfect matching in \(G\). Clearly, if \(G\) has a perfect matching \(M\), then \(G\) has an even order and the edge-induced subgraph \(G[M]\) is a \(1\)-regular spanning subgraph of \(G\). Any spanning subgraph of a graph \(G\) is referred to as a factor of \(G\). A \(k\)-regular factor is referred to as a \(k\)-factor. For instance, a \(1\)-factor of a graph \(G\) is the subgraph induced by a perfect matching in \(G\). A graph \(G\) is said to be factorable into the factors \(F_1,F_2,\ldots,F_t\) if these factors are (pairwise) edge-disjoint and \(\bigcup_{i=1}^{t} E_G(F_i) = E_G\). If \(G\) is factored into \(F_1,F_2,\ldots,F_t\), then \(\mathcal{F} = \{F_1,F_2,\ldots,F_t\}\) is called a factorisation of \(G\). If there exists a factorisation \(\mathcal{F}\) of a graph \(G\) such that each factor in \(\mathcal{F}\) is a \(k\)-factor (for a fixed positive integer \(k\)), then \(G\) is \(k\)-factorable.
It was shown in [11] that, for each positive integer \(n\), the complete graph \(K_{2n}\) is \(1\)-factorable. Now, let us consider a complete graph \(K_{2n}\) with a \(1\)-factor removed. It is easy to observe that these graphs are \(2n-2\)-regular graphs, and so the following observation can be made.
Observation 5.1. A graph \(G\) is a complete graph \(K_{2n}\) with a \(1\)-factor removed if and only if \(G\) is \(2n-2\)-regular graph (\(n \geq 1\)).
Notice that the complete graphs \(K_{2n}\) with \(1\)-factor removed are complete graphs \(K_{2n}\), where we remove a perfect matching. Figure 3 illustrates the complete graphs \(K_4\) and \(K_6\) with \(1\)-factor removed. It is easy to check that these graphs are \(2\)-vertex certified domination critical graphs.
Now, we characterise \(2\)-vertex certified domination critical graphs. We start with the following observation and lemma.
Observation 5.2. Let \(G\) be a graph. If \(G\) is a \(2\)-vertex certified critical graph, then for each vertex \(v\) of \(G\), the graph \(G' = G – v\) contains an universal vertex.
Lemma 5.3. Let \(G\) be a graph of order \(n\). If \(G\) is a \(2\)-vertex certified domination critical graph, then \(G\) is a \(n-2\)-regular graph and \(n\) is even.
Proof. Let \(G\) be a \(2\)-vertex certified domination critical graph. Let \(D_{{\rm cer}}\) be a \(\gamma_{{\rm cer}}\)-set of \(G\). Since \(|D_{{\rm cer}}| = 2\), let \(u,v \in D_{{\rm cer}}\). If \(u,v\) are shadowed vertices, then it follows that \(G = K_2\) or \(G = \overline{K_2}\). Now, assume that \(u,v\) are not shadowed vertices. Therefore, we may conclude that \(u,v \notin S_G\) and consequently \(S_G = \emptyset\). According to Theorem 3.13, we have \(pn[u,D_{{\rm cer}}] = \{u\}\) and \(pn[v,D_{{\rm cer}}] = \{v\}\). Then \(uv \notin E_G\) and \(N_G(u) = N_G(v)\) (otherwise, if \(N_G(u) \neq N_G(v)\), then \(u\) or \(v\) must contain a private neighbour, which is a contradiction). Since every vertex of \(N_G(u)\) belongs to the some \(\gamma_{{\rm cer}}\)-set \(D_{{\rm cer}}'\) and \(d_G(u) = n-2\), a similar argument as the one presented below leads to the conclusion that \(G\) is \(n-2\)-regular graph. As a consequence of the handshaking lemma, we conclude that the order \(n\) must be even. ◻
Now, considering Lemma 5.3 and Observation 5.1, we obtain the following theorem. Notably, a similar result was mentioned in [5].
Theorem 5.4. Let \(G\) be a graph of order \(n\). Then \(G\) is a \(2\)-vertex certified domination critical graph if and only if \(G = K_2\), \(G = \overline{K_2}\) or \(G\) is a complete graph \(K_{2n}\) with a \(1\)-factor removed for \(n \geq 1\).
We close this paper with a list of open problems that we have yet to settle.
Problem 5.5. Characterise the class of bipartite graphs \(G = ((A,B),E_G)\), in which \(\gamma_{{\rm cer}}(G) = \min\{|A|,|B|\}\).
Problem 5.6. Characterise the class of trees \(T\), in which \(\gamma_{{\rm cer}}(T) = \gamma(T)\).
Problem 5.7. Characterise the class of \(3\)-vertex certified domination critical graphs.
Problem 5.8. Characterise the certified stable vertices and certified domination stable graphs. Recall that a vertex \(v\) of a graph \(G\) is called certified stable if \(\gamma_{{\rm cer}}(G – v) \geq \gamma_{{\rm cer}}(G)\), while a graph \(G\) is called certified domination stable graph if all vertices of \(G\) are certified stable.
Problem 5.9. Identify an algorithm for checking equality \(\gamma_{{\rm cer}}(G) = |A|\) in bipartite graphs \(G = ((A,B);E_G) \ (1 \leq |A| \leq |B|)\).