Given a connected graph \(G=(V,E)\) of order \(n\ge 2\) and two distinct vertices \(u,v\in V(G)\), consider two operations on \(G\): the \(k\)-multisubdivision and the \(k\)-path addition. Let \(msd_{\gamma_c}(G)\) and \(pa_{\gamma_c}(G)\) denote, respectively, the connected domination multisubdivision and path addition numbers of \(G\). In both operations, \(k\) represents the number of vertices added to \(V(G)\), resulting in a new graph denoted by \(G_{u,v,k}\). We prove that \(\gamma_c(G) \le \gamma_c(G_{u,v,k})\) for \(k = msd_{\gamma_c}(G) \in \{1,2,3\}\) in the case of \(k\)-multisubdivision, where \(uv \in E(G)\). Additionally, we show that \(\gamma_c(G) – 2 \le \gamma_c(G_{u,v,k})\) for \(k = pa_{\gamma_c}(G) \in \{0,1,2,3\}\) in the case of \(k\)-path addition, where \(uv \notin E(G)\), and provide both necessary and sufficient conditions under which these inequalities hold.
Let \(G=(V, E)\) be a finite, simple, and connected graph with a vertex-set \(V(G)\) of order \(|V|=n\) and an edge-set \(E(G)\) of size \(|E|= m\). For any nonempty subset \(S\subset V(G)\), let \(G[S]\) denote the subgraph of \(G\) induced by \(S\). For any vertex \(v\) of \(G\), \(N(v)\) denotes the set of all neighbors of \(v\) in \(G\) and the closed neighborhood of \(v\) is the set \(N[v]=N(v)\cup \lbrace v \rbrace\). The private neighborhood of a vertex \(v\in S\) with respect to \(S\) is the set \(pn[v,S]=\lbrace u\in V(G): N[u]\cap S= \lbrace v \rbrace \rbrace\). Each vertex in \(pn[v,S]\) is called a private neighbor of \(v\) with respect to \(S\). Let \(\Delta(G)\) (respectively, \(\delta(G)\)) denote the maximum (respectively, minimum) degree in \(G\). Throughout this paper, the notations \(P_{n}\), \(C_{n}\), and \(K_{n}\) always denote a path, a cycle, and a complete graph of order \(n\), respectively. By \(P_{u,v}(G)\) we denote a path \(P_{n}\) with end vertices \(u\) and \(v\). For further basic notations and graph theory terminology, we refer the reader to the book of Berge [4].
Throughout the history of graph theory, understanding how domination parameter and its variants behave under specific structural modifications has been a central topic of investigation. In particular, considerable attention has been devoted to studying how operations such as subdividing an edge or adding a path between two distinct vertices affect the values of these parameters. These operations can be viewed as local structural transformations in a network, introducing intermediate or linking vertices while preserving the essential topology of the graph. Analyzing whether a domination parameter remains invariant (unchanging) or increases or decreases (changing) under these modifications provides deep insight into the stability and sensitivity of dominating sets. For an explicit introduction to the theory of domination, we refer the reader to the book by Haynes et al. [16]. The effect of edge subdivision on domination-type parameters in graphs was first explored by Haynes et al. [14, 15] for the classical domination and independence parameters, where the original problem leading to this study was introduced by Arumugam in a private communication to Haynes [14]. In the subsequent work on domination parameters, new studies were introduced by Bhattacharya and Vijayakumar [5], Favaron et al. [8], and more recently, Samodivkin [20] presented an explicit study of the behavior of the domination number when a path \(P_n\) is added to a graph. Following these papers, the focus shifted towards the total domination variant, where many authors investigated its behaviour. See, for example, the works of Haynes et al. [17, 18], Favaron et al. [11, 9], Avella-Alaminos et al. [3], and Çiftçi and Aytaç [7]. Several papers have also examined related topics in Roman domination, such as those by Khodkar et al. [19] and Atapour et al. [2, 1].
Despite this extensive research, the connected domination parameter still lacks explicit studies concerning the effects of the multisubdivision and path addition operations. A review of the literature suggests that the first and only paper addressing the impact of edge subdivision on the connected domination number is due to Favaron et al. [10], where the authors investigated the connected domination subdivision number, denoted by \(sd_{\gamma_c}(G)\) (each edge subdivided at most once). They established upper bounds for this parameter and characterized those graphs for which the inequality \(\gamma_c(G) + sd_{\gamma_c}(G) \leq n – 1\) holds, where \(\gamma_c(G)\) denotes the connected domination number of \(G\). For additional results and discussions related to the connected domination parameter, the reader is referred to Chellali et al. [6]. Consequently, there remains a clear gap in the literature regarding how these two operations affect the connected domination number and under which structural conditions this parameter remains invariant or changes. The goal of the present paper is therefore to investigate the effect of edge multisubdivision and path addition on the connected domination number by providing necessary and sufficient conditions for each possible change value.
A connected dominating set of a connected graph \(G\) is a subset \(D \subseteq V(G)\) such that every vertex of \(V(G) \setminus D\) is adjacent to at least one vertex in \(D\), and the induced subgraph \(G[D]\) is connected. The connected domination number of \(G\), denoted by \(\gamma_c(G)\), is the minimum cardinality of a connected dominating set in \(G\). A connected dominating set of \(G\) with cardinality \(\gamma_c(G)\) is called a \(\gamma_c\)-set of \(G\).
Let \(G\) be a connected graph and let \(uv\) be an edge of \(G\). By multisubdividing the edge \(uv\), we mean forming a graph \(H\) from \(G\) by adding \(k\) new vertices \(x_1, x_2, \dots, x_k\) and replacing the edge \(uv\) with the path \(u x_1, x_1 x_2, \dots, x_k v\). Formally, \[V(H) = V(G) \cup \{x_1, x_2, \dots, x_k\} \quad \text{and} \quad E(H) = (E(G) \setminus \{uv\}) \cup \{u x_1, x_1 x_2, \dots, x_k v\}.\]
The path addition operation is defined as the disjoint union of a connected graph \(G\) with a path \(P_k\), where the end vertices of this path are identified with two distinct vertices of \(G\). Formally, let \(u\) and \(v\) be distinct vertices of \(G\) and let \(P_k : x_1, x_2, \dots, x_k\) be a path of length \(k \ge 0\). The graph \(H\) is obtained from the disjoint union of \(G\) and \(P_k\) by identifying \(u\) with one end vertex of \(P_k\) and \(v\) with the other. Note that in a path addition, when \(u\) and \(v\) are nonadjacent and \(k = 0\), the operation simply corresponds to adding the edge \(uv\) to \(G\). The resulting graph from either operation is denoted by \(G_{u,v,k}\), where \(k\) is the number of newly added vertices to the original graph \(G\).
Fricke et al. [12] introduced the concept of \(\gamma_c\)-good and \(\gamma_c\)-bad vertices in graphs. A vertex \(v\) of a graph \(G\) is said to be \(\gamma_c\)-good if it belongs to some \(\gamma_c\)-set of \(G\), and \(\gamma_c\)-bad if it belongs to no \(\gamma_c\)-set of \(G\).
Let \(msd_{\gamma_c}(u,v)\) and \(pa_{\gamma_c}(u,v)\) denote the minimum integer \(k\) such that \(\gamma_c(G) \ne \gamma_c(G_{u,v,k})\) under the multisubdivision and path addition operations, respectively. For every connected graph \(G\) of order \(n \ge 2\), we define the minimum \(e\)-multisubdivision number (respectively, the minimum \(e\)-path addition number) with respect to connected domination, denoted by \(emsd_{\gamma_c}(G)\) (respectively, \(epa_{\gamma_c}(G)\)), as follows: \[\begin{aligned} emsd_{\gamma_c}(G) &= \min \{\, msd_{\gamma_c}(u,v) \mid u,v \in V(G),\ uv \in E(G) \,\},\\ epa_{\gamma_c}(G) &= \min \{\, pa_{\gamma_c}(u,v) \mid u,v \in V(G),\ uv \notin E(G) \,\}. \end{aligned}\]
Similarly, the maximum \(e\)-multisubdivision number (respectively, the maximum \(e\)-path addition number) with respect to connected domination, denoted by \(Emsd_{\gamma_c}(G)\) (respectively, \(Epa_{\gamma_c}(G)\)), is defined as \[\begin{aligned} Emsd_{\gamma_c}(G) &= \max \{\, msd_{\gamma_c}(u,v) \mid u,v \in V(G),\ uv \in E(G) \,\},\\ Epa_{\gamma_c}(G) &= \max \{\, pa_{\gamma_c}(u,v) \mid u,v \in V(G),\ uv \notin E(G) \,\}. \end{aligned}\]
If \(G\) is a complete or an edgeless graph, then the above numbers are not defined, and we write \[epa_{\gamma_c}(G) = Epa_{\gamma_c}(G) = \infty, \quad \text{and} \quad emsd_{\gamma_c}(G) = Emsd_{\gamma_c}(G) = \infty,\] respectively.
Throughout this paper, we assume that all graphs under consideration are connected. We end this section with some results and definitions which will be useful in proving our main results.
Definition 1.1. Let \(G = (V, E)\) be a connected graph. A vertex \(u \in V\) is called a cut-vertex of \(G\) if the removal of \(u\) disconnects the graph \(G\).
Lemma 1.2. Let \(G\) be a connected graph and let \(D\) be a \(\gamma_c\)-set of \(G\). A vertex \(u \in D\) if and only if one of the following holds:
\(\bullet\) \(u\) has at least one private neighbor in \(V \setminus D\) with respect to \(D\),
\(\bullet\) \(u\) is a cut-vertex of the induced subgraph \(G[D]\).
Proof. \(\Rightarrow\) Let \(D\) be a \(\gamma_c\)-set of \(G\) with \(|D| = \gamma_c(G)\), and let \(u \in D\). Suppose, to the contrary, that \(u\) has no private neighbor in \(V \setminus D\) and that \(u\) is not a cut-vertex of \(G[D]\). Then every vertex in \(N(u)\) is either adjacent to another vertex of \(D\) or belongs to \(D\) entirely, implying that \(D – \{u\}\) is still a connected dominating set of \(G\), contradicting the minimality of \(D\). Hence, \(u\) must have at least one private neighbor in \(V\setminus D\) or \(u\) is a cut-vertex of \(G[D]\).
\(\Leftarrow\) If \(u\) has at least one private neighbor in \(V\setminus D\), then clearly \(u \in D\), since otherwise that neighbor would not be dominated by \(D\). On the other hand, if \(u\) is a cut-vertex of \(G[D]\), then \(G[D – \{u\}]\) is disconnected, implying that \(D – \{u\}\) cannot be a connected dominating set of \(G\). Therefore, \(u\) must belong to the \(\gamma_c\)-set \(D\) of \(G\). ◻
The concept of a cut-vertex was first formalized by Whitney [21] in his study of non-separable graphs, and later popularized under its modern terminology by Harary [23].
Remark 1.3. A cut-vertex \(v\) may or may not have a private neighbor.
Remark 1.4. A cut-vertex in \(G[D]\) can only lie on a path of \(G[D]\).
The following Lemma describes all possible membership configurations of two adjacent vertices in a \(\gamma_c\)-set of a connected graph \(G\).
Lemma 1.5. Let \(G\) be a connected graph and let \(u,v\) be adjacent vertices of \(G\). Fix a \(\gamma_c\)-set \(D\) of \(G\). Exactly one of the following cases occurs:
(A) \(u,v\in D\), and the edge \(uv\) is contained in a cycle of \(G[D]\).
(B) \(u,v\in D\), and the edge \(uv\) lies on a path of \(G[D]\).
(C) \(u\in D\), \(v\notin D\), \(u\) is \(\gamma_c\)-good, \(v\) is \(\gamma_c\)-bad, and \(v\) is a private neighbor of \(u\) with respect to \(D\) (i.e. \(N(v)\cap D=\{u\}\)).
(D) \(u\in D\), \(v\notin D\), \(u\) is \(\gamma_c\)-good, \(v\) is \(\gamma_c\)-bad, and \(v\) has at least two neighbors in \(D\) (i.e. \(|N(v)\cap D|\ge 2\)).
(E) \(u\in D\), \(v\notin D\), and both \(u\) and \(v\) are \(\gamma_c\)-good, with \(v\) not being a private neighbor of \(u\) with respect to \(D\) (i.e. \(|N(v)\cap D|\ge 2\), but \(v\) belongs to another \(\gamma_c\)-set).
(F) \(u,v\notin D\) (both \(u\) and \(v\) are \(\gamma_c\)-bad\()\).
Proof. Let \(G\) be connected, let \(D\) be a \(\gamma_c\)-set of \(G\), and let \(u,v\) be adjacent vertices of \(G\). Each of \(u\) and \(v\) either belongs to \(D\) or does not. Then we have:
Case 1. \(u,v\in D\). Then \(uv\in G[D]\). If \(uv\) belongs to a cycle of \(G[D]\), we obtain case (A). Otherwise, \(uv\) lies on a path of \(G[D]\), which corresponds to case (B).
Case 2. Without loss of generality, \(u\in D\) and \(v\notin D\). Since \(D\) is a minimal connected dominating set, every vertex outside \(D\) is dominated by at least one vertex of \(D\), hence \(N(v)\cap D\neq\emptyset\). Two situations arise depending on the status of \(v\):
\(\bullet\) If \(v\) is a \(\gamma_c\)-bad vertex, then it belongs to no \(\gamma_c\)-set of \(G\). By definition of domination, we have \(|N(v)\cap D|\ge 1\). If \(|N(v)\cap D|=1\), then \(v\) is a private neighbor of \(u\) in \(D\), giving case (C). If \(|N(v)\cap D|\ge 2\), we obtain case (D).
\(\bullet\) If \(v\) is a \(\gamma_c\)-good vertex, then it belongs to some other \(\gamma_c\)-set of \(G\). Therefore, \(|N(v)\cap D|\ge 2\). Otherwise, if \(|N(v)\cap D|=1\), \(v\) would be a private neighbor of its unique dominator \(u\) in \(D\), which would prevent \(v\) from belonging to any \(\gamma_c\)-set. This yields case (E).
Case 3. \(u,v\notin D\). If this holds for every \(\gamma_c\)-set \(D\) of \(G\), then both vertices are \(\gamma_c\)-bad, which corresponds to case (F).
Since the above cases are mutually exclusive and cover all possible membership configurations of \(u\) and \(v\) with respect to \(D\), exactly one of (A)–(F) must hold. ◻
Lemma 1.6. Let \(G\) be a connected graph of order \(n\geq 2\), \(uv\in E(G)\) and let \(G_{u,v,k}\) be obtained from \(G\) by multisubdividing \(uv\) with \(k\geq 1\) new vertices. Let \(D\) be a \(\gamma_c\)-set of \(G\) with \(u,v\in D\). If the edge \(uv\) belongs to some path of \(G[D]\), then \[\gamma_c(G_{u,v,k}) \ge \gamma_c(G) + 1.\]
Proof. We have that \(\gamma_c(G)=|D|\). Since \(u,v\in D\) and \(uv\) is a bridge of \(G[D]\), the removal of the edge \(uv\) disconnects \(G[D]\) into at least two components. In \(G_{u,v,k}\) every vertex of \(V(G)\) has a neighbour in \(D\) by definition of \(D\). However, the edge \(uv\) is replaced by the path \(u, x_1, \dots, x_k, v\). Because \(uv\) was a bridge of \(G[D]\), there is no \(u,v\)-path inside \(G[D]\) that avoids the edge \(uv\). Consequently the induced subgraph \(G_{u,v,k}[D]\) is disconnected. Any connected dominating set of \(G_{u,v,k}\) must induce a connected subgraph and must dominate all vertices. Thus, one must include \(k\) vertices from the path joining \(u\) and \(v\) in \(G_{u,v,k}\) for \(k\geq 1\). Thus any \(\gamma_c\)-set of \(G_{u,v,k}\) has size at least \(|D|+1\), so \(\gamma_c(G_{u,v,k}) \geq |D|+1 = \gamma_c(G)+1\). ◻
Lemma 1.7. Let \(G\) be a connected graph of order \(n\geq 2\), \(uv\in E(G)\) and let \(G_{u,v,k}\) be obtained from \(G\) by multisubdividing \(uv\) with \(k\geq 1\) new vertices. Let \(D\) be a \(\gamma_c\)-set of \(G\) with \(u,v\in D\). If the edge \(uv\) belongs to some cycle of \(G[D]\), then \[\gamma_c(G_{u,v,k}) = \gamma_c(G) \ \text{for} \ k=1,2 \ \text{and} \ \gamma_c(G_{u,v,k}) \ge \gamma_c(G) + 1 \ \text{for} \ k\geq 3.\]
Proof.Let \(M\) be a \(\gamma_{c}\)-set of \(G\) such that \(u, v \in M\) and the edge \(uv\) belongs to a cycle in \(G[M]\). In the graph \(G_{u,v,2}\), every vertex of \(V(G)\) remains dominated by \(M\). Moreover, since \(x_1\) is dominated by \(u\) and \(x_2\) is dominated by \(v\), the set \(M\) is also a \(\gamma_{c}\)-set of \(G_{u,v,2}\) (by the same argument as in the case \(k=1\)). For \(k \ge 3\), we add exactly \(k-2\) new vertices to the set \(M\) so that \(G[M]\) remains connected. Consequently, for \(k \ge 3\), we obtain \(\gamma_c(G_{u,v,k}) \ge \gamma_c(G) + 1\). ◻
Lemma 1.8. Let \(G\) be a connected graph of order \(n\ge 2\), let \(D\) be a \(\gamma_c\)-set of \(G\) with \(u\in D\), and let \(v\) be a \(\gamma_c\)-bad vertex of \(G\). Let \(G_{u,v,k}\) be the graph obtained from \(G\) by multisubdividing the edge \(uv\) with \(k\ge 1\) new vertices. If \(v\in pn[u,D]\), then \[\gamma_c(G_{u,v,k}) \ge \gamma_c(G) + 1.\]
Proof.Let \(\gamma_c(G)=|D|\) and assume \(v\in pn[u,D]\), so \(N(v)\cap D=\{u\}\). In \(G\) the vertex \(v\) is dominated only by \(u\in D\). After multisubdivision the edge \(uv\) is replaced by the path \(u, x_1\cdots x_k ,v\), so \(u\) is no longer adjacent to \(v\) in \(G_{u,v,k}\). Consequently, \(v\) is not dominated by \(D\) in \(G_{u,v,k}\) anymore. Then, any connected dominating set of \(G_{u,v,k}\) must therefore contain \(k\) vertices from the set \(\lbrace x_1,\dots,x_k \rbrace\), because \(x_k\) dominates \(v\) in \(G_{u,v,k}\). Therefore, every connected dominating set of \(G_{u,v,k}\) has size at least \(|D|+1=\gamma_c(G)+1\). That is, \(\gamma_c(G_{u,v,k}) \geq \gamma_c(G)+1\). ◻
The remainder of this paper is organized as follows. In Section 2, we prove that \(msd_{\gamma_c}(G) \in \{1, 2, 3\}\) for every edge \(uv \in E(G)\). In Section 3, we show that \(pa_{\gamma_c}(G) \in \{0, 1, 2, 3\}\) for every pair of nonadjacent vertices \(u, v \notin E(G)\).
In this section, we denote by \(G_{u,v,k}\) the graph obtained by multisubdivising the edge \(uv\). The aim is to prove that \(msd_{\gamma_{c}}(G)\in\lbrace 1,2,3\rbrace\) by providing necessary and sufficient conditions, where \(uv\in E(G)\) for any connected graph \(G\) of order \(n\geq 2\).
Theorem 2.1. Let \(u\) and \(v\) be adjacent vertices of a graph \(G\). Then \(\gamma_{c}(G)\leq \gamma_{c}(G_{u,v,1})\leq \gamma_{c}(G)+1\). Moreover,
(I) \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) if and only if one of the following holds:
\((a)\) both \(u\) and \(v\) are included in every \(\gamma_{c}\)-set of \(G\) and the edge \(uv\) belongs to a cycle in the subgraph induced by these \(\gamma_{c}\)-sets,
\((b)\) \(u\) and \(v\) are \(\gamma_{c}\)-good and \(\gamma_{c}\)-bad vertices of \(G\), respectively. \(u\) is included in every \(\gamma_c\)-set of \(G\), where the vertex \(v\) is not a private neighbor of \(u\) with respect to the \(\gamma_c\)-set,
\((c)\) both \(u\) and \(v\) are \(\gamma_{c}\)-good vertices of \(G\) and every \(\gamma_{c}\)-set contains only one of them. Without loss of generality, \(v\) is dominated by at least another vertex besides \(u\),
(II) \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\) if and only if one of the following is true:
\((d)\) both \(u\) and \(v\) are included in every \(\gamma_{c}\)-set of \(G\) and the edge \(uv\) belongs to no cycle in the subgraph induced by these \(\gamma_{c}\)-sets,
\((e)\) \(u\) is a \(\gamma_{c}\)-good vertex, \(v\) is a \(\gamma_{c}\)-bad vertex, and every \(\gamma_{c}\)-set of \(G\) contains \(u\), such that \(v\) is a private neighbor of \(u\) with respect to these \(\gamma_{c}\)-sets,
\((f)\) both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\).
Proof. \((a)\) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) with \(\gamma_c(G)= \mid D \mid\) and \(u,v\in D\). By (A) of Lemma 1.5, the edge \(uv\) belongs to a cycle of \(G[D]\). Suppose, to the contrary, that the edge \(uv\) belongs to no cycle in \(G[D]\). Now, according to Lemma 1.6, we have \(\gamma_c(G_{u,v,k})\ge\gamma_c(G)+1\) for \(k\geq 1\), a contradiction. Then, the edge \(uv\) must belongs to a cycle in \(G[D]\).
\((a)\) \(\Leftarrow\) The rest follows by Lemma 1.7.
\((b)\) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) holds and \(D\) is a \(\gamma_{c}\)-set of \(G\) such that \(u\in D\) and \(v\) is a \(\gamma_{c}\)-bad vertex of \(G\). Suppose, to the contrary, that \(v\) is a private neighbor of \(u\) with respect to \(D\), then following Lemma 1.8, we obtain that \(\gamma_c(G_{u,v,k}) \geq \gamma_c(G) + 1\) for \(k\geq 1\), a contradiction. Thus \(\mid N(v) \cap D\mid \geq 2\).
\((b)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) with \(u, w\in M\) and \(v\) is a \(\gamma_{c}\)-bad vertex of \(G\) such that \(v\) is adjacent to both vertices \(u\) and \(w\) in the set \(M\). In the graph \(G_{u,v,1}\), we have that \(x_{1}\in pn[u,M]\) and \(v\in pn[w,M]\). Thus \(M\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\) and \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\).
\((c)\) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) holds and \(D\) is a \(\gamma_{c}\)-set of \(G\) such that both \(u\) and \(v\) are \(\gamma_{c}\)-good vertices of \(G\). Now, without loss of generality, assume that \(u\in D\) and \(v\in pn[u,D]\). Then, in this case, \(v\) cannot be \(\gamma_{c}\)-good vertex of \(G\), thus it is a \(\gamma_{c}\)-bad vertex and according Lemma 1.8, \(\gamma_{c}(G_{u,v,k}) \geq \gamma_{c}(G)+1\) for \(k\geq 1\), a contradiction. Then, \(v\) is a \(\gamma_{c}\)-good vertex and \(\mid N(v)\cap D\mid\geq 2\).
\((c)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) and both \(u\) and \(v\) are \(\gamma_{c}\)-good vertices of \(G\). Without loss of generality, let \(u\in M\) and \(\mid N(v)\cap M\mid\geq 2\), then in the graph \(G_{u,v,1}\), the vertex \(x_{1}\) is dominated by \(u\) and \(v\) is dominated by some other vertices in \(M-\lbrace u\rbrace\), which means that \(M\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\) and \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\).
\((d)\) \(\Rightarrow\) Let \(D\) be a \(\gamma_c\)-set of \(G\) with \(u,v \in D\). Since the edge \(uv\) is included in a path of \(G[D]\), then Lemma 1.6 is fullfiled and \(\gamma_{c}(G_{u,v,1}) = \gamma_{c}(G)+1\) for \(k=1\).
\((d)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) with \(u,v\in M\) and the edge \(uv\) belongs to a path in \(G[M]\). In the graph \(G_{u,v,1}\), it is obvious that \(M\cup\lbrace x_{1}\rbrace\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\). Hence \(\gamma_{c}(G_{u,v,k})=\mid M\cup\lbrace x_{1}\rbrace\mid=\gamma_{c}(G)+1\).
\((e)\) \(\Rightarrow\) This case follows from Lemma 1.8 for \(k=1\) such that \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\).
\((e)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) with \(u\in M\), \(v\notin M\), \(v\) is a \(\gamma_c\)-bad vertex, and \(v\in pn[u,M]\). In the graph \(G_{u,v,1}\), the set \(M\) dominates all the vertices of the set \(V(G_{u,v,1})-\lbrace v\rbrace\). Therefore, \(M\cup\lbrace x_{1}\rbrace\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\) such that \(\gamma_{c}(G_{u,v,1})=\mid M\cup\lbrace x_{1}\rbrace\mid=\gamma_{c}(G)+1\).
\((f)\) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\) holds and \(D\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\). Without loss of generality, the set \(D-\lbrace u\rbrace\) is a \(\gamma_{c}\)-set of \(G\) since \(x_{1}\in pn[u,D]\) such that \(\mid D-\lbrace u\rbrace\mid=\gamma_{c}(G)\). Thus \(\gamma_{c}(G_{u,v,1})=\mid D \mid=\gamma_{c}(G)+1\).
\((f)\) \(\Leftarrow\) Let both \(u\) and \(v\) be \(\gamma_{c}\)-bad vertices of \(G\). Let \(M\) be a \(\gamma_{c}\)-set of \(G\) and \(U\) a \(\gamma_{c}\)-set of \(G_{u,v,1}\). The set \(M\) dominates all the vertices of the set \(V(G_{u,v,1})-\lbrace x_{1}\rbrace\), hence one of \(u\) and \(v\) must be included in \(U\). Then, \(U=M\cup\lbrace u \rbrace\) or \(U=M\cup\lbrace v \rbrace\) are both \(\gamma_{c}\)-sets of \(G_{u,v,1}\) and \(\gamma_{c}(G_{u,v,1})=\mid U\mid=\gamma_{c}(G)+1\). ◻
The following Figures 2–9 illustrate all the possible cases described in Theorem 2.1.
Theorem 2.2. Let \(u\) and \(v\) be adjacent vertices of a graph \(G\). Then \(\gamma_{c}(G)\leq \gamma_{c}(G_{u,v,2})\leq \gamma_{c}(G)+2\). Moreover,
(I) \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)\) if and only if both \(u\) and \(v\) are included in every \(\gamma_{c}\)-set of \(G\) and the edge \(uv\) belongs to a cycle in the subgraph induced by these \(\gamma_{c}\)-sets,
(II) \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)+1\) if and only if \(u\) is a \(\gamma_{c}\)-good vertex and \(v\) is either \(\gamma_{c}\)-good or \(\gamma_{c}\)-bad in \(G\). In the case where both \(u\) and \(v\) are \(\gamma_{c}\)-good vertices, every \(\gamma_{c}\)-set of \(G\) contains exactly one of them. Without loss of generality, \(v\) is dominated by at least two vertices.
(III) \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)+2\) if and only if one of the following holds:
\((a)\) \(u\) is a \(\gamma_{c}\)-good vertex, \(v\) is a \(\gamma_{c}\)-bad vertex, and every \(\gamma_{c}\)-set of \(G\) contains \(u\), such that \(v\) is a private neighbor of \(u\) with respect to these \(\gamma_{c}\)-sets,
\((b)\) both \(u\) and \(v\) are in every \(\gamma_{c}\)-set of \(G\) and the edge \(uv\) belongs to no cycle in the subgraph induced by these \(\gamma_{c}\)-sets,
\((c)\) both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\).
Proof. (I) \(\Rightarrow\) Suppose that \(\gamma_{c}(G_{u,v,2}) = \gamma_{c}(G)\) holds. Let \(D\) be a \(\gamma_{c}\)-set of \(G\) such that \(u,v \in D\), and assume that the edge \(uv\) belongs to a path in \(G[D]\). Then Lemma 1.6 applies, implying that \(\gamma_{c}(G_{u,v,k}) > \gamma_{c}(G)\) for all \(k \geq 1\), a contradiction.
(I) \(\Leftarrow\) The converse follows from Lemma 1.7.
(II) \(\Rightarrow\) Suppose that \(\gamma_{c}(G_{u,v,2}) = \gamma_{c}(G) + 1\) holds, and let \(D\) be a \(\gamma_{c}\)-set of \(G\). According to parts \((b)\) and \((c)\) of Theorem 2.1, in the graph \(G_{u,v,2}\) and without loss of generality, suppose \(u \in D\) and \(v \notin D\), we obtain that \(D \cup \lbrace x_{1} \rbrace\) and \(D \cup \lbrace v \rbrace\) are both \(\gamma_{c}\)-sets of \(G_{u,v,2}\) such that \(\gamma_{c}(G_{u,v,2}) = \mid D \cup \lbrace x_{1} \rbrace \mid = \mid D \cup \lbrace v \rbrace\mid = \gamma_{c}(G) + 1\).
(II) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\). Without loss of generality, assume that \(u \in M\), \(v \notin M\), and \(\mid N(v) \cap M\mid \geq 2\). In the graph \(G_{u,v,2}\), the vertex \(u\) dominates \(x_{1}\), while \(v\) is dominated by some vertices in \(M \setminus \{u\}\). Hence, all vertices of \(M\) are adjacent to every vertex of \(V(G_{u,v,2}) \setminus \{x_{2}\}\). Consequently, \(M \cup \{x_{1}\}\) and \(M \cup \{v\}\) are both \(\gamma_{c}\)-sets of \(G_{u,v,2}\), and \(\gamma_{c}(G_{u,v,2}) = \mid M \cup \{x_{1}\} \mid = \gamma_{c}(G) + 1\).
\((a)\) \(\Rightarrow\) This direction follows from
Lemma 1.8 for
\(k = 2\), which gives \(\gamma_{c}(G_{u,v,2}) = \gamma_{c}(G) +
2\).
\((a)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) such that \(u
\in M\), \(v \notin M\), and
\(v \in pn[u,M]\). Since \(v\) is adjacent only to \(u\) in \(M\), it follows that the set \(M \cup \lbrace x_{1}, x_{2} \rbrace\) is a
\(\gamma_{c}\)-set of \(G_{u,v,2}\), and \(\gamma_{c}(G_{u,v,2}) = \mid M \cup \lbrace x_{1},
x_{2} \rbrace \mid = \gamma_{c}(G) + 2\).
\((b)\) \(\Rightarrow\) This follows from Lemma 1.6 for \(k=2\), and we obtain \(\gamma_{c}(G_{u,v,2})=\mid D\cup\lbrace x_{1}, x_{2}\rbrace\mid=\gamma_{c}(G)+2\).
\((b)\) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) with \(u,v\in M\) and the edge \(uv\) belongs to a path in \(G[M]\). Now, by \((d)\) of Theorem 2.1 and since \(N(x_{1})=\lbrace u, x_{2}\rbrace\) and \(N(x_{2})=\lbrace x_{1}, v\rbrace\), we arrive at the fact that \(M\cup\lbrace x_{1}, x_{2}\rbrace\) is a \(\gamma_{c}\)-set of \(G_{u,v,2}\) in which \(\gamma_{c}(G_{u,v,2})=\mid M\cup\lbrace x_{1}, x_{2}\rbrace\mid=\gamma_{c}(G)+2\).
\((c)\) \(\Rightarrow\) Suppose that \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)+2\) holds, and let \(D\) be a \(\gamma_{c}\)-set of \(G_{u,v,1}\). According to \((f)\) of Theorem 2.1, we have \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\). Hence, \(\gamma_{c}(G)\in\lbrace \mid D-\lbrace u\rbrace\mid , \mid D-\lbrace v\rbrace\mid \rbrace\). That is, both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\). Now, without loss of generality, let \(u\in D\) and \(v\notin D\). Then \(D\) dominates all vertices of \(V(G_{u,v,2})-\lbrace x_{2}\rbrace\). Therefore, one of \(x_{1}\) and \(v\) must be included in any \(\gamma_{c}\)-set of \(G_{u,v,2}\), and \(\gamma_{c}(G_{u,v,2})=\mid D\cup\lbrace x_{1}\rbrace\mid=\mid D\cup\lbrace v\rbrace\mid=\gamma_{c}(G)+2\).
\((c)\) \(\Leftarrow\) Let both \(u\) and \(v\) be \(\gamma_{c}\)-bad vertices of \(G\). Since each of them is adjacent to some vertex of the \(\gamma_{c}\)-set \(M\) of \(G\), in the graph \(G_{u,v,2}\), the set \(M\) dominates \(V(G_{u,v,2})-\lbrace x_{1}, x_{2}\rbrace\). This implies that \(M\cup\lbrace u,x_{1}\rbrace\) and \(M\cup\lbrace v,x_{2}\rbrace\) are both \(\gamma_{c}\)-sets of \(G_{u,v,2}\), and \(\gamma_{c}(G_{u,v,2})=\mid M\cup\lbrace u,x_{1}\rbrace\mid=\gamma_{c}(G)+2\). ◻
The following Figures 10–15 illustrate all the possible cases described in Theorem 2.2.
Theorem 2.3. Let \(u\) and \(v\) be adjacent vertices of a graph \(G\). Then \(\gamma_{c}(G_{u,v,3})\geq\gamma_{c}(G)+1\).
Proof. From Lemma 1.5, we have exactly six possible cases. By Lemmas 1.6, 1.7, and 1.8, we know that for \(k\geq 3\), \(\gamma_c(G_{u,v,k}) \geq \gamma_c(G)+1> \gamma_c(G)\). On the other hand, if \(u\in D\), \(v\notin D\) and \(\mid N(v)\cap D\mid \geq 2\), then \(D\cup\lbrace v, x_{1}\rbrace\), \(D\cup\lbrace x_{1}, x_{2}\rbrace\), and \(D\cup\lbrace v, x_{3}\rbrace\) are all \(\gamma_{c}\)-sets of \(G_{u,v,3}\) such that \(\gamma_{c}(G_{u,v,3})=\mid D\cup\lbrace v, x_{1}\rbrace \mid=\gamma_{c}(G)+2>\gamma_{c}(G)\). Finally, if both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\), then \(D\cup\lbrace u,v,x_{1}\rbrace\) is one of many other \(\gamma_{c}\)-sets of \(G_{u,v,3}\) such that \(\gamma_{c}(G_{u,v,3})=\mid D\cup\lbrace u,v,x_{3}\rbrace \mid = \gamma_{c}(G)+3>\gamma_{c}(G)\). In conclusion, in each case, at least three vertices among \(u\), \(v\), \(x_{1}\), \(x_{2}\), and \(x_{3}\) are included in any \(\gamma_{c}\)-set of \(G_{u,v,3}\), which always leads to the fact that \(\gamma_{c}(G_{u,v,3})\geq\gamma_{c}(G)+1\). ◻
Corollary 2.4. Let \(u\) and \(v\) be adjacent vertices of a graph \(G\) of order \(n\geq 3\), then
(i) \(Emsd_{\gamma_{c}}(G)=1\) if and only if \(\gamma_{c}(G)=1\).
(ii) If \(\gamma_{c}(G)=2\) and \(G\) contains a \(\gamma_{c}-set\) such that \(N(u)\cap N(v)=\emptyset\). Then, \(Emsd_{\gamma_{c}}(G)=1\).
(iii) If \(d_{G}(u)=d_{G}(v)=2\), then \(Emsd_{\gamma_{c}}(G)=1\).
Proof. \((i)\) \(\Rightarrow\) Let \(Esd_{\gamma_{c}}(G)=1\) hold and \(\gamma_{c}(G)=1\). Then there exists a vertex \(u\in V(G)\) such that \(d_{G}(u)=n-1\). Now, in the graph \(G_{u,v,1}\), we know that \(d_{G_{u,v,1}}(v)\leq n-2\) for all vertices of \(V(G_{u,v,1})\), which means that \(u\) is no longer a universal vertex in \(G_{u,v,1}\). Therefore, any \(\gamma_{c}\)-set of \(G_{u,v,1}\) must contain at least two vertices. Thus, \(\gamma_{c}(G_{u,v,1})\geq 2\).
(i) \(\Leftarrow\) Let \(\gamma_{c}(G)=1\). It is obvious that for all \(k\geq 1\), \(\gamma_{c}(G_{u,v,k})>\gamma_{c}(G)\).
(ii) Let \(\gamma_{c}(G)=2\) and \(D\) is a \(\gamma_{c}\)-set of \(G\) such that \(N(u)\cap N(v)=\emptyset\). In the graph \(G_{u,v,1}\), \(D\cup \lbrace x_{1} \rbrace\) is a \(\gamma_{c}\)-set if \(u,v \in D\). If \(u,v \notin D\), then \(D\cup \lbrace u \rbrace\) and \(D\cup \lbrace v \rbrace\) are both \(\gamma_{c}\)-sets. If \(u\in D\) and \(v\notin D\), then at least one of the vertices \(v\), \(x_{1}\), or those in \(N(u)\cup N(v)\) must be included in the \(\gamma_{c}\)-set of \(G_{u,v,1}\). Hence, in every case, \(\gamma_{c}(G_{u,v,1})\geq 3>\gamma_{c}(G)\).
(iii) Let \(D\) be a \(\gamma_{c}\)-set of \(G\), and let \(u\) and \(v\) be adjacent vertices of degree \(2\) in the graph \(G\). That is, the vertices \(u\) and \(v\) are part of a path \(P_{k}\) in \(G\). Therefore, according to \((d)\) of Theorem 2.1, \(\gamma_{c}(G_{u,v,1})>\gamma_{c}(G)\). ◻
The following Figures 16–20 illustrate all the possible cases described in Corollary 2.4.
Corollary 2.5. Let \(u\) and \(v\) be adjacent vertices of a graph \(G\) of order \(n\geq 3\). Then,
(iv) \(Emsd_{\gamma_{c}}(G)=1\) for any complete graph \(K_{n}\), star \(K_{1,n-1}\), wheel \(W_{n}\), or any connected graph with a universal vertex.
(v) \(Emsd_{\gamma_{c}}(G)=1\) for any complete bipartite graph \(K_{p,q}\) with \(p,q\geq 2\).
(vi) \(Emsd_{\gamma_{c}}(G)=1\) for any cycle \(C_{n}\) or path \(P_{n}\).
Proof. Statements \((iv)\), \((v)\), and \((vi)\) follow immediately from \((i)\), \((ii)\), and \((iii)\) of Corollary 2.4, respectively. ◻
Corollary 2.6. Let \(T\) be a tree of order \(n\geq 3\). Then, \(Emsd_{\gamma_{c}}(T)=1\).
Proof. Since every tree \(T\) is acyclic, each edge \(uv\in E(T)\) lies on a path in \(T\). Let \(D\) and \(M\) be \(\gamma_{c}\)-sets of \(T\) and \(T_{u,v,1}\), respectively. In the tree \(T_{u,v,1}\), there exists at least one leaf vertex that is not dominated by any set of cardinality \(\mid D\mid=\gamma_{c}(T)\). Therefore, \(M=D\cup\lbrace x_{1}\rbrace\) is a \(\gamma_{c}\)-set of \(T_{u,v,1}\) such that \(\gamma_{c}(T_{u,v,1})=\mid D\cup\lbrace x_{1}\rbrace\mid > \gamma_{c}(T)\). ◻
In this section, we denote by \(G_{u,v,k}\) the graph obtained by the addition of a path \(P_{k}\) whose end vertices are two distinct vertices \(u\) and \(v\) of \(G\). We shall prove that \(pa_{\gamma_{c}}(G)\in\lbrace 0,1,2,3\rbrace\) by establishing necessary and sufficient conditions for \(0\leq epa_{\gamma_{c}}(G) \leq Epa_{\gamma_{c}}(G)\leq 3\), where \(uv\notin E(G)\) for any connected graph \(G\) of order \(n\geq 3\).
Theorem 3.1. Let \(u\) and \(v\) be non-adjacent vertices, and \(t\) and \(w\) be adjacent vertices of a graph \(G\) of order \(n\geq 6\), and let \(D\) be a \(\gamma_{c}\)-set of \(G\) with \(u,t,w,v \in D\). If \(t\) and \(w\) are cut-vertices of \(G[D]\) with no private neighbors with respect to \(D\), then \(\gamma_{c}(G_{u,v,0})=\gamma_{c}(G)-2\).
Proof. Let \(D\) be a \(\gamma_{c}\)-set of \(G\) with \(u,v,t,w\in D\), and let the path \(P_{u,v}\) of \(G[D]\) contains the adjacent vertices \(t\) and \(w\) (both are cut-vertices of \(G[D]\)). In the graph \(G_{u,v,0}\) obtained by adding the edge \(uv\) to \(G\), a new cycle is formed. If at least one of them has a private neighbor in \(V-D\), then it cannot be removed from the dominating set \(D\). Now, Since the vertices of the set \(D-\lbrace t,w \rbrace\) are adjacent to all vertices of \(V(G_{u,v,0}) \setminus (D-\lbrace t,w \rbrace)\), we arrive at \(\gamma_{c}(G_{u,v,0})=\mid D-\lbrace w,t \rbrace \mid=\gamma_{c}(G)-2\). ◻
The following Figure 21 illustrates the case described in Theorem 3.1.
Theorem 3.2. Let \(u\) and \(v\) be non-adjacent vertices, and let \(D\) be a \(\gamma_{c}\)-set of \(G\). If one of the following conditions holds:
(a) \(u,w\in D\), \(w\) is not a cut-vertex in the graph \(G-\lbrace v \rbrace\), and \(v\) is the only private neighbor of \(w\) with respect to \(D\),
(b) \(u,v,w\in D\) and \(w\) is a cut-vertex of \(G[D]\) with no private neighbors with respect to \(D\), then \(\gamma_{c}(G_{u,v,0})=\gamma_{c}(G)-1\).
Proof.(a) Let \(D\) be a \(\gamma_{c}\)-set of \(G\) with \(u,w\in D\) such that \(pn[w,D]=\lbrace w,v\rbrace\), where \(w\) is not a cut-vertex of \(G[D]\) (according to Lemma 1.2, \(w\) has a private neighbor with respect to \(D\)). In the graph \(G_{u,v,0}\), obtained by adding the edge \(uv\) to \(G\), the vertex \(v\) becomes adjacent to both \(u\) and \(w\). Since \(w\) is adjacent to at least one vertex in \(D\), the set \(D-\lbrace w\rbrace\) forms a \(\gamma_{c}\)-set of \(G_{u,v,0}\), and therefore \(\gamma_{c}(G_{u,v,0})=\mid D-\lbrace w\rbrace\mid=\gamma_{c}(G)-1\).
(b) This case follows from Theorem 3.1. ◻
The following Figures 22 and 23 illustrate all the possible cases described in Theorem 3.2.
Theorem 3.3. Let \(u\) and \(v\) be non adjacent vertices of a graph \(G\) of order \(n\geq 3\), then \(\gamma_{c}(G)\leq \gamma_{c}(G_{u,v,1}) \leq \gamma_{c}(G)+1\). Moreover,
(a) \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) if and only if at least one of \(u\) and \(v\) is included in every \(\gamma_{c}\)-set of \(G\).
(b) \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\) if and only if both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\).
Proof. (a) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\) holds, and let \(D\) be a \(\gamma_{c}\)-set of \(G\). Suppose, to the contrary, that both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\). Then one of them must be included in any \(\gamma_{c}\)-set \(D'\) of \(G_{u,v,1}\). That is, \(\gamma_{c}(G_{u,v,1})=\mid D' \mid=\mid D\cup \lbrace u\rbrace\mid=\mid D\cup \lbrace v\rbrace\mid=\gamma_{c}(G)+1\), which contradicts the original hypothesis. Therefore, at least one \(u\) and \(v\) must be a \(\gamma_{c}\)-good vertex of \(G\).
(a) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\). First, let \(u\in M\) and \(v\notin\) is a \(\gamma_{c}\)-good or bad vertex of \(G\). Then in \(G_{u,v,1}\), since \(v\) is adjacent to some vertices of \(M-\lbrace u\rbrace\) and \(x_{1}\in pn[u,M]\), then \(M\) is a \(\gamma_{c}\)-set of \(G_{u,v,1}\), in which \(\gamma_{c}(G_{u,v,1})=\mid M \mid=\gamma_{c}(G)\). Now, if \(u,v\in M\), it is obvious that \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\).
(b) \(\Rightarrow\) Let \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)+1\) holds. Suppose, to the contrary, that at least one of \(u\) and \(v\) belongs to some \(\gamma_c\)-set of \(G\). Then \((a)\) of Theorem 3.3 is fullfiled and \(\gamma_{c}(G_{u,v,1})=\gamma_{c}(G)\), a contradiction. Then, both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\).
(b) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) and both \(u\) and \(v\) are \(\gamma_{c}\)-bad vertices of \(G\). In the graph \(G_{u,v,1}\), we know that \(N(x_{1})=\lbrace u,v\rbrace\). Thus both the sets \(M\cup \lbrace u\rbrace\) and \(M\cup \lbrace v\rbrace\) are \(\gamma_{c}\)-sets of \(G_{u,v,1}\) such that \(\gamma_{c}(G_{u,v,1})=\mid M\cup \lbrace u\rbrace \mid = \mid M\cup \lbrace v\rbrace \mid =\gamma_{c}(G)+1\). ◻
The following Figures 24–26 illustrate all the possible cases described in Theorem 3.3.
Thoerem 3.4. Let \(u\) and \(v\) be non adjacent vertices of a graph \(G\) of order \(n\geq 3\), then \(\gamma_{c}(G)\leq \gamma_{c}(G_{u,v,2}) \leq \gamma_{c}(G)+2\). Moreover,
\((a)\) \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)\) if and only if both \(u\) and \(v\) are included in every \(\gamma_{c}\)-set of \(G\).
\((b)\) \(\gamma_{c}(G)+1 \leq \gamma_{c}(G_{u,v,2})\leq\gamma_{c}(G)+2\) if and only if every \(\gamma_{c}\)-set of \(G\) contains at most one of \(u\) and \(v\).
Proof. (a) \(\Rightarrow\) This implication follows by applying the same reasoning as in \((a)\) of Theorem 3.3, in the case where both \(u\) and \(v\) are included in every \(\gamma_{c}\)-set of \(G\).
(a) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\) such that \(u,v\in M\). In the graph \(G_{u,v,2}\), we have \(x_{1}\in pn[u,M]\) and \(x_{2}\in pn[v,M]\). Hence, \(M\) remains a \(\gamma_{c}\)-set of \(G_{u,v,2}\), and therefore \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)\).
(b) \(\Rightarrow\) Let \(\gamma_{c}(G)+1 \leq \gamma_{c}(G_{u,v,2})\leq\gamma_{c}(G)+2\) holds. Suppose, to the contrary, that \(u,v\in D\), then \((a)\) of Theorem 3.4 is fulfilled and \(\gamma_{c}(G_{u,v,2})=\gamma_{c}(G)\), a contradiction. Then every \(\gamma_c\)-set of \(G\) contains at most one of \(u\) and \(v\).
(b) \(\Leftarrow\) Let \(M\) be a \(\gamma_{c}\)-set of \(G\). If \(u\in M\) and \(v\notin M\), then in \(G_{u,v,2}\), \(x_{2}\) is not dominated by any of the vertices of \(M\). Thus \(M\cup \lbrace x_{1} \rbrace\) and \(M\cup \lbrace v \rbrace\) are both \(\gamma_{c}\)-sets of \(G_{u,v,2}\) and \(\gamma_{c}(G_{u,v,2})=\mid M\cup \lbrace v \rbrace \mid =\gamma_{c}(G)+1\). Now, if \(u,v\notin M\), then both \(x_{1}\) and \(x_{2}\) are not dominated by \(M\). That is, \(M\cup \lbrace u,v \rbrace\) is a \(\gamma_{c}\)-set of \(G_{u,v,2}\) and \(\gamma_{c}(G_{u,v,2})=\mid M\cup \lbrace u,v \rbrace \mid = \gamma_{c}(G)+2\). Hence, \(\gamma_{c}(G)+2 \geq \gamma_{c}(G_{u,v,2})\geq \gamma_{c}(G)+1\). ◻
The following Figures 27–29 illustrate all the possible cases described in Theorem 3.9.
Theorem 3.5. Let \(u\) and \(v\) be non adjacent vertices of a graph \(G\) of order \(n\geq 3\), then \(\gamma_{c}(G_{u,v,3})\geq\gamma_{c}(G)+1\).
Proof. Let \(D\) be a \(\gamma_{c}\)-set of \(G\). If \(u,v\in D\), then in the graph \(G_{u,v,3}\), the set \(D\) dominates all vertices in \(V(G_{u,v,3})-\lbrace x_{2} \rbrace\). Thus, both \(D\cup \lbrace x_{1} \rbrace\) and \(D\cup \lbrace x_{3} \rbrace\) are \(\gamma_{c}\)-sets of \(G_{u,v,3}\), and consequently \(\gamma_{c}(G_{u,v,3})=\mid D\cup \lbrace x_{1} \rbrace \mid=\gamma_{c}(G)+1\). Now, if \(u\in D\) and \(v\notin D\), then in \(G_{u,v,3}\), the set \(D\) dominates all vertices in \(V(G_{u,v,3})-\lbrace x_{2}, x_{3} \rbrace\). Hence, the sets \(D\cup \lbrace x_{1}, v\rbrace\), \(D\cup \lbrace x_{1}, x_{2}\rbrace\), and \(D\cup \lbrace x_{3}, v\rbrace\) are all \(\gamma_{c}\)-sets of \(G_{u,v,3}\), and we have \(\gamma_{c}(G_{u,v,3})=\mid D\cup \lbrace x_{1}, v\rbrace \mid=\gamma_{c}(G)+2\). Finally, if \(u,v\notin D\), then \(D\) dominates all vertices in \(V(G_{u,v,3})-\lbrace x_{1}, x_{2}, x_{3}\rbrace\). Therefore, \(D\cup\lbrace u, x_{1}, v \rbrace\) is a \(\gamma_{c}\)-set of \(G_{u,v,3}\), and \(\gamma_{c}(G_{u,v,3})=\mid D\cup\lbrace u, x_{1}, v \rbrace \mid=\gamma_{c}(G)+3\). Hence, \(\gamma_{c}(G_{u,v,3})\geq\gamma_{c}(G)+1\). ◻
Corollary 3.6. Let \(T\) be a tree of order \(n \geq 4\) and let \(D\) be its \(\gamma_{c}\)-set. Let \(u\) and \(v\) be two non-adjacent vertices of \(T\).
(i) If \(u\) is either a root or a support vertex of \(T\), \(w\) is a support vertex, and \(v\) is a leaf such that \(N(v)=\lbrace w\rbrace\), then \(\gamma_{c}(T_{u,v,0})=\gamma_{c}(T)-1\).
(ii) If both \(u\) and \(v\) are non-leaf vertices of \(T\) such that the path \(P_{u,v}\) contains one or two adjacent support vertices having no neighbors in \(V-D\), then \(\gamma_{c}(T_{u,v,0}) \in \lbrace \gamma_{c}(T)-1, \gamma_{c}(T)-2 \rbrace\), respectively.
(iii) If both \(u\) and \(v\) are leaves, then \(Epa_{\gamma_{c}}(T)=1\).
Proof. (i) Let \(D\) be a \(\gamma_{c}\)-set of \(T\) and suppose \(u,w\in D\) with \(pn[w,D]=\lbrace w, v\rbrace\). Since the support vertex \(w\) is adjacent to some vertices in \(D\), in \(T_{u,v,0}\) the vertex \(v\) becomes dominated by \(u\). By Lemma 1.2, \(w\) is no longer a cut-vertex in \(T_{u,v,0}\), and thus \(D-\lbrace w\rbrace\) forms a \(\gamma_{c}\)-set of \(T_{u,v,0}\) with \(\gamma_{c}(T_{u,v,0})=\mid D-\lbrace w\rbrace\mid=\gamma_{c}(T)-1\).
(ii) This follows immediately from Theorems 3.1 and 3.2.
(iii) This follows directly from part \((b)\) of Theorem 3.3. ◻
Corollary 3.7. Let \(u\) and \(v\) be two non-adjacent vertices of a graph \(G\) containing a universal vertex. Then \(Epa_{\gamma_{c}}(G)=1\).
Proof. Let \(w\in V(G)\) be a universal vertex, so that \(d_{G}(w)=n-1\) and \(\gamma_{c}(G)=1\). In the graph \(G_{u,v,1}\), for every vertex \(t\in V(G_{u,v,1})\), we have \(d_{G_{u,v,1}}(t)\leq n-2\). Hence, \(G_{u,v,1}\) contains no universal vertices, which implies that for any \(\gamma_{c}\)-set \(M\) of \(G_{u,v,1}\), we have \(\gamma_{c}(G_{u,v,1})=\mid M\mid \geq 2>\gamma_{c}(G)=1\). Thus, \(Epa_{\gamma_{c}}(G)=1\). ◻
Corollary 3.8. For any cycle \(C_{n}\) with \(n\geq 4\), we have \(Epa_{\gamma_{c}}(C_{n})=0\), and \[\gamma_{c}(C'_{n}) \in \lbrace \gamma_{c}(C_{n})-1,\ \gamma_{c}(C_{n})-2 \rbrace,\] where \(C'_{n}=(V(C_{n}), E(C_{n})\cup \lbrace uv \rbrace )\).
Proof. An immediate consequence of Theorems 3.1 and 3.2. ◻
The behavior of the parameter \(\gamma_{c}(G)\) under the edge multisubdivision operation depends, in some cases, on the structure of the subgraph induced by the \(\gamma_{c}\)-sets, and in others, on the membership of the end vertices of the subdivided edge in the \(\gamma_c\)-sets of \(G\). In general, seven possible distinct cases corresponding to this operation are presented in Lemma 1.5. Under the path addition operation, the behavior of \(\gamma_{c}(G)\) primarily depends on the nature of the end vertices of the added path, particularly on whether they are \(\gamma_{c}\)-good or \(\gamma_{c}\)-bad vertices of \(G\).
The authors would like to thank the reviewers for their valuable remarks and suggestions to improve the original manuscript. The authors did not receive support from any organization for the submitted work.
The authors declare that they have no conflict of interest.