Critical and stable pendant domination

1. Introduction

Consider a connected graph with a finite number of nodes. Then, the concept of pendant domination was defined in motivation to the idea of isolated domination in graphs. The parameter pendant domination lies between dominating and connected sets in a graph since a \(\gamma-\) set requires no backup for the nodes. In contrast, a connected dominating set requires backup for every node in the set. However, in the concept of pendant domination, at least the node should have a backup. This article analyzes the effect of \(\gamma_{pe}(G)\) when an arbitrary node or edge is removed.

The analysis of the impact of eliminating a point or an edge on any graph-theoretic variable has a significant idea in the field of networks. That is, analyzing the removal of a point is more vital as a significant thought in a network's topological plan is fault tolerance, which means the performance of the network's ability to provide service despite defective components. In the presence of a fault, the activity of the network can be determined by calculating the impact that eliminating an edge or a point from its underlying graph \(G\) has on the fault-tolerance criterion. For more details of applications on vertex and edge removal, we refer [1,2,3]. Hence the changes on \(\gamma(G)\) when \(G\) is changed by eliminating a point or eliminating or expansion of an edge were studied by so many researchers.

The analysis of effect of domination parameter is given in Chapter 5 of Haynes et al., [4]. In this article we begin a similar study corresponding to the pendant domination number of a graph.

Let the graph \(G\) be any nontrivial simple graph with \(n\) nodes and \(m\) edges. The open neighborhood of a nodes \(v\) is indicated by \(N(v)\) and is the set having all the nodes incident to \(v\). The closed neighborhood of the nodes \(v\) is indicated by \(N[v]\) and is the set having all set nodes incident to the node \(v\) along with the node \(v\). The least degree of a vertex in a graph is indicated by \(\delta(G)\) and highest of the degree of a graph is indicated by \( \Delta (G)\). If \(\delta(G)= \Delta(G)\), then \(G\) is referred as a regular graph. If degree of the node \(v\) is \(0\), then \(v\) is referred as an isolated node of \(G\) and the degree of the node \(u\) is \(1\), then \(u\) is called a pendant node. For basic terminologies of graph and domination, see [5,6]. An edge \(e={uv}\) is contiguous to a node of degree one is referred as a pendant edge.

The following definition and results are required for our study;

Definition 1. A dominating set \(S\) of \(G\) is referred as a pendant dominating set if the graph induced by \(S\) having minimum one node of degree one. The least cardinality of a pendant dominating set in \(G\) is referred as the pendant domination number of \(G\), indicated by \(\gamma_{pe}(G)\) [7].

Theorem 1.[7] If \(P_n\) is a path graph with \(n\) nodes and \(n \geq 2\). Then \[\gamma_{pe}(P_n) = \left\{ \begin{array}{lll} \,\,\frac{n}{3} + 1, & \hbox{ if \(n \equiv 0 (mod 3)\);} \\ \lceil \frac{n}{3}\rceil, & \hbox{ if \(n \equiv 1 (mod 3)\);} \\ \lceil{ \frac{n}{3}} \rceil +1 , & \hbox{ if \(n \equiv 2 (mod 3)\).} \end{array} \right.\]

Theorem 2.[7] If \(C_n\) is a cycle graph with \(n\) nodes and \(n \geq 3\). Then \[\gamma_{pe}(C_n) = \left\{ \begin{array}{lll} \,\,\frac{n}{3} + 1, & \hbox{ if \(n \equiv 0 (mod 3)\);} \\ \lceil \frac{n}{3}\rceil, & \hbox{ if \(n \equiv 1 (mod 3)\);} \\ \lceil{ \frac{n}{3}} \rceil +1 , & \hbox{ if \(n \equiv 2 (mod 3)\).} \end{array} \right.\]

2. Vertex removal

We observe that the pendant domination parameter value of a graph \(G\) may increase or decrease or remain same when a point is removal from \(G\). For example, in a complete graph \(K_m\) \((m>2)\) or complete bipartite graph \(K_{m,n}\), removal of any one point it does not affect the value of \(\gamma_{pe}\). In a sunlet graph the removal of a node of degree one it decreases the value of \(\gamma_{pe}\) by one. In barbell graph \(v_1,v_2\) are the adjacent nodes connected two copies of complete graphs. The removal of the nodes \(v_1\) in barbell graph increases the value of \(\gamma_{pe}\) by 2. Hence we can define the point set \(V(G)\) of \(G\) into three subsets, \begin{equation} V_{pe}^0=\{v\in V: \gamma_{pe}(G-v) = \gamma_{pe}(G)\},\\ \end{equation} \begin{equation} V_{pe}^-=\{v\in V: \gamma_{pe}(G-v) < \gamma_{pe}(G)\},\\ \end{equation} \begin{equation} V_{pe}^+=\{ v\in V: \gamma_{pe}(G-v) > \gamma_{pe}(G)\}. \end{equation}

Remark 1. There is a graph such that the sets \(V_{pe}^0, V_{pe}^-\) and \(V_{pe}^+\) are nonempty. For example for the graph \(G\) given in Figure 1, we have \(V_{pe}^0=\{4\}\), \(V_{pe}^-=\{7\}\) and \(V_{pe}^+=\{3\}\).

Theorem 3. If \(G \cong P_n\) and \(n\geq 3\), then we have

• (i) If \(n \equiv 0(mod3)\) or \(n \equiv 1(mod3)\), then \[v_i \in \left\{ \begin{array}{ll} V_{pe}^o , & \hbox{if \(i=1\) or \(n\);} \\\\ V_{pe}^+ , & \hbox{if \(i \equiv 2\) or \(3 (mod3)\).} \end{array} \right.\]
• (ii) If \(n \equiv 2(mod3)\), then \[v_i \in \left\{ \begin{array}{lll} V_{pe}^- , & \hbox{if \(i=1\) or \(n\);} \\\\ V_{pe}^+ , & \hbox{if \(i \equiv 0(mod3)\);}\\\\ V_{pe}^0 , & \hbox{if \(i \equiv 2 (mod3)\).} \end{array} \right.\]

Proof. Case (i) \(n \equiv 0\,\, or\, 1\,\,(mod\,3)\).

If \(n=3k\) or \(n=3k+1\), for \(k>0\). Then by Theorem 1, \(\gamma_{pe}(P_n)=k+1\). Here, we can be easily identified that deleting of any one pendant nodes \(v_i\), where \(i=1\) or \(i=n\) in \(P_n\) the value of \(\gamma_{pe}\) is unalter. If we removal of any one internal nodes \(v_i\), where \(i\equiv1\, or\, 2\, or\, 3(mod\,3)\), then the path \(P_n\) splits into two paths \(P_{r_1}\) and \(P_{r_2}\) such that either \(r_1 \equiv 0(mod\,3)\) and \(r_2 \equiv2(mod\,3)\) or \(r_1 \equiv1(mod\,3)\) and \(r_2 \equiv1(mod3)\). It can easily verified that \(\gamma_{pe}(P_{r_1})+\gamma_{pe}(P_{r_2})= k+2=\gamma_{pe}(P_n)+1\). Thus \(\gamma_{pe}(P_n-v) = \gamma_{pe}(P_n)+1\) and therefore \(v \in V^+_{pe}\), \(\forall \,v \in V(P_n)\).

Case (ii) \(n \equiv 2(mod\,3)\).

If \(n=3k+2\) for some \(k>0\). Then by Theorem 1 \(\gamma_{pe}(P_n)=k+2\). If we removal of any one pendant nodes \(v_1\) or \(v_n\) in \(P_n\), then the value of \(\gamma_{pe}(P_n)\) is decreases by one i.e., \(\gamma_{pe}(P_n-v)=\gamma_{pe}(P_{n-1})=k+1 < \gamma_{pe}(P_n)\). Thus, \(v_i \in V_{pe}^-\).

If we removal of any one internal nodes \(v_i\) where \(i\equiv 0 (mod3)\), then the path spilt into two paths \(P_{3k_1-1}\) and \(P_{3k_2+2}\) for some positive integers \(k_1\) and \(k_2\) such that \(k_1+k_2=k\). Now \(\gamma_{pe}(P_n-v_i)=\gamma_{pe}(P_{3k_1-1})+\gamma_{pe}(P_{3k_2+2})=(k_1+1)+(k_2+2)=\gamma_{pe}(P_n)+1\). Therefore \(v_i\in V^+_{pe}\). If \(i\equiv 1\, \text{or} \,2 (mod3)\) then removal of any one internal nodes in \(P_n\) the path splits into two paths \(P_{3k_1}\) and \(P_{3k_2+1}\), where \(k_1,k_2 >0\) and \(k_1+k_2=k\). Now \(\gamma_{pe}(P_n-v_i)=\gamma_{pe}(P_{3k_1})+\gamma_{pe}(P_{3k_2+1})=(k_1+1)+(k_2+1)=(k+2)=\gamma_{pe}(P_n)\). Therefore \(v_i \in V^0_{pe}\).

Theorem 4. If \(C_n\) is a cycle with \(n\geq 4\) nodes, then \[V(C_n) \in \left\{ \begin{array}{ll} V_{pe}^- , & \hbox{if \(n \equiv 2(mod3)\);} \\\\ V_{pe}^o , & \hbox{otherwise.} \end{array} \right.\]

Proof. If \(n=3k+2\) for some \(K>0\). Then by Theorem 2 \(\gamma_{pe}(C_n)= k+2\). If we removal of a nodes in \(C_n\), then \(\gamma_{pe}(C_n-v)=\gamma_{pe}(P_{3k+1})= k+1 < k+2= \gamma_{pe}(C_n)\). Therefore, \(V=V^-_{pe}\). Now, if \(n=3k\), then again by Theorem 2, \(\gamma_{pe}(C_n)=k+1\) and for any nodes \(v\) in \(C_n\), \(\gamma_{pe}(C_n-v)=\gamma_{pe}(P_{3k-1})= k+1= \gamma_{pe}(C_n)\) and so, \(V=V^o_{pe}\). In a same method we can directly verified that \(V=V^o_{pe}\) when \(n=3k+1\).

3. Edge removal

In this section, we analyze the impact of edge removal in the \(\gamma_{pe}(G)\) domination number of the graph \(G\). As in the previous scenario of nodes removal, we can observe that the pendant domination number \(\gamma_{pe}(G)\) of a graph \(G\) may increment or diminish or stay same when an edge is deleting from \(G\). Hence we can segment the edge set \(E(G)\) of \(G\) into \(3\) subsets \(E_{pe}^+ ,E_{pe}^-\) and \(E_{pe}^0\) as below, \begin{equation} E_{pe}^-=\{(u,v)\in E: \gamma_{pe}(G-uv) \le \gamma_{pe}(G)\},\\ \end{equation} \begin{equation} E_{pe}^0=\{(u,v)\in E: \gamma_{pe}(G-uv) = \gamma_{pe}(G)\},\\ \end{equation} \begin{equation} E_{pe}^+=\{(u,v)\in E: \gamma_{pe}(G-uv) \ge \gamma_{pe}(G)\}. \end{equation}

Theorem 5. Let \(P_n\) be a path graph with \(n\geq3\) nodes, then we have

• (i) If \(n \equiv 0\,(mod\,3)\), then \[(v_i,v_{i+1}) \in \left\{ \begin{array}{ll} E_{pe}^- , & \hbox{if \(i= n-1\)}; \\\\ E_{pe}^+ , & \hbox{if \(i \equiv 0 (mod3)\)};\\\\ E_{pe}^o , & \hbox{if \(i \equiv 1 (mod3)\).} \end{array} \right.\]
• (ii) If \(n \equiv 1\,(mod\,3)\), then \[(v_i,v_{i+1}) \in \left\{ \begin{array}{lll} E_{pe}^0 , & \hbox{if \(i \equiv 2 (mod3)\) or \(i=1\) or \(n-1\);} \\\\ E_{pe}^+ , & \hbox{if \(i \equiv 0\) or \(1 (mod3)\).} \end{array} \right.\]
• (ii) If \(n \equiv 2(mod3)\), then \[(v_i,v_{i+1}) \in \left\{ \begin{array}{lll} E_{pe}^- , & \hbox{if \(i=1\) or \(n-1\);} \\\\ E_{pe}^0 , & \hbox{otherwise.} \end{array} \right.\]

Proof. Case (i) \(n \equiv 0(mod\,3)\)

If \(n\) is a non-negative integer, then \(n=3k\). Then by Theorem 1, \(\gamma_{pe}(P_n)=k+1\). Here, we can easily confirmed that removal of an edge \(e=(v_i, v_{i+1})\), where \(i=1\) or \(i=n-1\) then the value of \(\gamma_{pe}\) is decreased by one. Therefore \(e \in E_{pe}^-\). Now removal of an edge \(e \in (v_i,v_{i+1})\), where \(i \equiv 0(mod3)\) then, the path splits in to two paths \(P_{3k_1-1}\) and \(P_{3k_2+2}\) for some positive integers \(k_1\) and \(k_2\) such that \(k_1+k_2=k\). Now \(\gamma_{pe}(P_n-e)=\gamma_{pe}(P_{3k_1-1})+\gamma_{pe}(P_{3k_1+2})=(k_1+1)+(k_2+2)=\gamma_{pe}+2\). Therefore \(e \in E_{pe}^+\). If we remove the edge \(e \in (v_i,v_{i+1})\), where \(i \equiv 1(mod3)\) then, the path splits into two paths \(P_{3k_1}\) and \(P_{3k_2+1}\) for some \(k_1, k_2 >0\) such that \(k_1+k_2=k-1\). Therefore \(\gamma_{pe}(P_n-e)=\gamma_{pe}(P_{3k_1})+\gamma_{pe}(P_{3k_2+1})=(k_1+1)+(k_2+1)=k+1=\gamma_{pe}(P_n)\). Thus \(e\in E_{pe}^0\).

Case (ii) \(n \equiv 1(mod\,3)\)

If \(n=3k+1\) for non negative integer \(k\). Then by Theorem 1, \(\gamma_{pe}(P_n)=k+1\). Now, removal of an edge \(e \in (v_i,v_{i+1})\) where \(i \equiv 0\, \text{or}\, 1 (mod3)\) then the path splits into two paths \(P_{3k_1-1}\) or \(P_{3k_1}\) and \(P_{3k_2}\) or \(P_{3k_2-1}\) for some positive integer \(k_1\) and \(k_2\) such that \(k_1+k_2=k\). Now \(\gamma_{pe}(P_n-e)=\gamma_{pe}(P_{3k_1-1})+\gamma_{pe}(P_{3k_2})=(k_1+1)+(k_2+1)=\gamma_{pe}(P_n)+1\). Thus \(e\in E_{pe}^+\). If we removal the edge \(e \in (v_i,v_{i+1})\), where \(i=1\) or \(i=n-1\) or \(i \equiv2(mod3)\) then, the value of \(\gamma_{pe}(P_n)\) is unaltered. Therefore \(e\in E_{pe}^0\).

Case (iii) \(n \equiv 2(mod\,3)\)

Let \(n=3k+2\) for non negative integer \(k\). Then by Theorem 1, \(\gamma_{pe}(P_n)=k+2\). Now, removal of an edge \(e \in (v_i,v_{i+1})\), where \(i=1\) or \(i=n-1\) then it is simple to verify that the value of \(\gamma_{pe}\) is decreased by one. Therefore \(e\in E_{pe}^-\). If we remove the edge \(e \in (v_j,v_{j+1})\) where \(j\equiv0\,(mod3)\) or \(j\equiv1\,(mod3)\) or \(j\equiv2\,(mod3)\) then the path splits into two paths \(P_{l_1}\) and \(P_{l_2}\) such that either \(l_1 \equiv-1(mod3)\) and \(l_2 \equiv 1(mod3)\) or \(l_1 \equiv0\,(mod3)\) and \(l_2 \equiv 0(mod3)\). It can be easily verified that \(\gamma_{pe}(P_{l_1})+\gamma_{pe}(P_{l_2})=\gamma_{pe}(P_n)\). Thus \(\gamma_{pe}(P_n-e)=\gamma_{pe}(P_n)\) and therefore \(e \in E_{pe}^0\).

Theorem 6. Let \(C_n\) be a cycle with \(n\geq 4\) nodes, then we have \begin{equation} E(C_n) = \left\{ \begin{array}{ll} E_{pe}^0 , & \hbox{if \(n \equiv 1 (mod3)\);}\\\\ E_{pe}^- , & \hbox{Otherwise}. \end{array} \right. \end{equation}

Proof. If \(n=3k+1\), then by Theorem 2, \(\gamma_{pe}(C_n)=k+1\) and consequently \(\gamma_{pe}(C_n-e)=\gamma_{pe}(P_{3k-1})=k+1\). So \(e \in E_{pe}^0\). Now, suppose \(n=3k\) then by Theorem 2, \(\gamma_{pe}(C_n)=k+1\) and for any edge \(e\) in \(C_n\) then \(\gamma_{pe}(C_n-e)=\gamma_{pe}(P_{3k-2})=k\). So \(e\in E_{pe}^- \). Now similar way we can directly verify if \(n=3k+2\).

Theorem 7. If \(G\) is a graph having exactly one node of degree zero and \(x \in V^+_{pe}\) and \(y \in V^-_{pe}\), then there is no edge between \(x\) and \(y\).

Proof. Assume that \(x \in V^+_{pe}, y \in V^-_{pe}\) and \((xy) \in E(G)\). Now let \(S'\) be a pendant dominating set of \(G-y\). If \(S'\) contains \(x\), then \(S'\) is a pendant dominating set of \(G\) which contradicts the cardinality of \(\gamma_{pe}(G)\). On the other hand, if \(S'\) does not having the node \(x\), then \(S' \cup \{y\}\) will be a pendant dominating set but does not contain \(x\). This is an inconsistency to the condition (ii) of Theorem 3 and hence the required result follows.

Theorem 8. If \(G\) is a graph without a node of degree zero, \(\gamma_{pe}(G) \neq \gamma_{pe}(G-v)\), for each node \(v\) in \(V(G)\), then \(V=V^-_{pe}\).

Proof. Suppose \(\gamma_{pe}(G) \neq \gamma_{pe}(G-v)\) \( \forall v \in V\). Then, clearly \(V^o_{pe}= \emptyset\). Now let us claim that \(V^+_{pe}= \emptyset\). Assume \(v\) is a node in \(V^+_{pe}\). As a result of the condition (i) of Theorem 3, that \(v\) is in each \(\gamma_{pe}-\) set \(S\) of \(G\). Let \(u\) be the neighbor of \(v\) in \(V-S\). As the node \(u\) does not belong to the set \(S\), again by condition (i) of Theorem 3, we have \(u \notin V^+_{pe}\). Also since \(u\) and \(v\) are incident nodes, by Theorem 3, \(u \notin V^-_{pe}\). Since \((v \in V^+_{pe})\). Hence \(u \in V^0_{pe}\). This contradiction completes the proof.

4. Edge addition

When an arbitrary edge is added then the pendant domination number remains unchanged. For an example in complete graph if we add an arbitrary edge to any one nodes of complete graph then the value of \(\gamma_{pe}\) does not alter. \[UEA \Longrightarrow \{\gamma_{pe}(G +e) = \gamma_{pe}(G) \,\, \forall e \in E(G)\}.\]

Theorem 9. Let \(G\) be graph and \(G \in UEA\) iff \(V^-_{pe} = \emptyset\).

Proof. Let \(G \in UEA\) and suppose a node \(x\) in \(G\) belongs to the set \(V^-_{pe}\). Thus, \(\gamma_{pe}(G-x) < \gamma_{pe}(G)\). Let \(S\) be a \(\gamma_{pe}-\) set of \(G-x\). Then adding edge \(xy\) for any \(y \in S\) gives \(\gamma_{pe}(G+xy) < \gamma_{pe}(G)\). This is a contradiction to the condition \(G \in UEA\).

Conversely, suppose \(G\) has no nodes in \(V^-_{pe}\) and \(\gamma_{pe}(G+uv) = \gamma_{pe}(G)- 1\) for some couple of nonadjacent nodes \(u\) and \(v\). Then any minimum pendant dominating set \(S\) of \(G+uv\) should contain either \(u\) or \(v\), say \(v\). Hence \(S\) dominates \(G-u\). Thus \(u \in V^-_{pe}\), a contradiction.

5. Conclusion

Nowadays, the study of domination-related parameters is an important area in graph theory, and many scholars are working in this area. Moreover, the theory of pendant domination is a required graph theory field with many practical applications. In this article, we investigated the impact of the evacuation of a node or an edge on any graph.

Conflicts of Interest:

"The author declares no conflict of interest".

Data Availability:

No data is required for this research.

Funding Information:

No funding is available for this research.