Influence of the Edge Removal, Edge Addition and Edge Subdivision on the Double Vertex–Edge Domination Number of a Graph

Abstract

A vertex v of a graph $G=(V,E)$ is said to ve-dominate every edge incident to v, as well as every edge adjacent to these incident edges. A set $S \subseteq V$ is a vertex–edge dominating set (double vertex–edge dominating set, respectively) if every edge of E is ve-dominated by at least one vertex (at least two vertices) of S. The minimum cardinality of a vertex–edge dominating set (double vertex–edge dominating set, respectively) of G is the vertex–edge domination number $\gamma _{ve}(G)$ (the double vertex–edge domination number $\gamma _{dve}(G)$, respectively). The influence of edge removal, edge addition and edge subdivision on the double vertex–edge domination number of a graph are investigated in this paper.

Let $G=(V,E)$ be a simple graph. The open neighborhood of a vertex $v\in V$ is $N(v)=\{u\in V\mid uv\in E\}$ and the closed neighborhood is $N[v]=N(v)\cup \{v\}$. The degree of a vertex v is the cardinality of its open neighborhood, denoted $d_{G}(v)=|N(v)|$. A vertex of degree one is called a leaf and its neighbor is called a support vertex. An edge incident with a leaf is called a pendant edge.

A subset $D \subseteq V(G)$ is a dominating set of G if every vertex of $V(G) {\setminus} D$ has a neighbor in D. The domination number of a graph G, denoted by $\gamma (G)$, is the minimum cardinality of a dominating set of G. For a comprehensive survey of domination in graphs, refer [1, 2].

In a graph G, a vertex dominates itself and its neighbors. A subset $S \subset V(G)$ is a double dominating set of G, abbreviated as DDS, if every vertex in $V - S$ has at least two neighbors in S and every vertex of S has a neighbor in S. The double domination number $\gamma _{2}(G)$ is the minimum cardinality of a double dominating set of G. A double domination set of G with minimum cardinality is called a $\gamma _{2}(G)$-set. Double domination was introduced by Harary and Haynes [3] and was further studied for a class of graphs by Chellali [4].

A vertex v ve-dominates every edge uv incident to v, as well as every edge adjacent to these incident edges, that is, a vertex v ve-dominates every edge incident to a vertex in N[v]. A set $S\subseteq V$ is a vertex–edge dominating set (or a ve-dominating set) if for every edge $e\in E$, there exists a vertex $v\in S$ such that v ve-dominates e. The minimum cardinality of a ve-dominating set of G is called the vertex–edge domination number $\gamma _{ve}(G)$. The concept of vertex–edge domination was introduced by Peters [5] in 1986 and studied further in [6,7,8].

A set $D \subseteq V$ is a double vertex–edge dominating set (or simply, a double ve-dominating set) of G, abbreviated as DVEDS, if every edge of E is ve-dominated by at least two vertices of D. The double vertex–edge domination number of G, denoted by $\gamma _{dve}(G)$, is the minimum cardinality of a double ve-dominating set of G. A double ve-dominating set of G of minimum cardinality is called a $\gamma _{dve}(G)$-set.

It is well known that the removal of an edge does not decrease the domination number $\gamma$ and increases it by at most one. That is, for any edge e of G, $\gamma (G) \le \gamma (G-e) \le \gamma (G)+1$. Here we present similar inequalities for a double vertex–edge domination number $\gamma _{dve}$ on edge removal, edge addition and edge subdivision.

FormalPara Theorem 1.1

For every graph G and any edge e of G we have $\gamma _{dve}(G)-1 \le \gamma _{dve}(G-e) \le \gamma _{dve}(G)+2$.

FormalPara Proof

We first prove that $\gamma _{dve}(G-e) \le \gamma _{dve}(G)+2$ for any edge $e=uv$. Let D be a minimum DVEDS of G. We consider three cases.

FormalPara Case 1

Assume that $u,v \notin D$. Then D is a DVEDS of the graph $G-e$ and $\gamma _{dve}(G-e) \le \left| D\right| \le \gamma _{dve}(G) < \gamma _{dve}(G)+2$.

FormalPara Case 2

Now let $\left| \{u,v\} \cap D\right| =1$. Without loss of generality assume that $u \in D$. Thus $D \cup \{v\}$ is a DVEDS of the graph $G-e$. We have $\gamma _{dve}(G-e) \le \left| D\right| +1 \le \gamma _{dve}(G)+1 < \gamma _{dve}(G)+2$.

FormalPara Case 3

Now let $u,v \in D$. The vertex u dominates the edges incident at v and the vertex v dominates the edges incident at u. In the graph $G-e$, the set $D \cup \{a,b\}$ where $a \in N(u){\setminus} \{v\}$ and $b \in N(v){\setminus} \{u\}$ is a DVEDS. Thus $\gamma _{dve}(G-e) \le \left| D\right| +2 \le \gamma _{dve}(G)+2$. Moreover the set $N(u){\setminus} \{v\}$ and $N(v){\setminus} \{u\}$ are not simultaneously empty. For in that case $G=K_2$ and $G-e = 2K_1$. Without loss of generality assume $N(u){\setminus} \{v\}$ is non empty. Then $(D \cup \{a\}){\setminus} \{v\}$ is a DVEDS of the graph $G-e$. We have $\gamma _{dve}(G-e) \le \left| D\right| -1+1 = \left| D\right| \le \gamma _{dve}(G) < \gamma _{dve}(G)+2$.

We now prove that $\gamma _{dve}(G)-1 \le \gamma _{dve}(G-e)$. Let $D'$ be a minimum DVEDS of the graph $G-e$, where $e=uv$ is an edge of G. Let us first assume that both $u,v \in D'$. Then $D'$ is a DVEDS of the graph G. Thus $\gamma _{dve}(G)-1 \le \left| D'\right| -1 \le \gamma _{dve}(G-e) - 1 < \gamma _{dve}(G-e)$.

Now assume that $\left| \{u,v\} \cap D'\right| =1$. Without loss of generality assume $u \in D'$. To dominate the edges incident with v in G, the vertex $v \in D'$. Thus $D' \cup \{v\}$ is a DVEDS of the graph G. Thus $\gamma _{dve}(G) \le \left| D'\right| +1 \le \gamma _{dve}(G-e) +1$. We have $\gamma _{dve}(G)-1 \le \gamma _{dve}(G-e)$.

Assume that both $u,v \notin D'$. If u is a pendant vertex in $G-e$, then the support vertex adjacent to $u \in D'$. Thus $D' \cup \{u\}$ is a DVEDS of the graph G. We have $\gamma _{dve}(G) \le \left| D'\right| +1 \le \gamma _{dve}(G-e)+1$. This gives $\gamma _{dve}(G)-1 \le \gamma _{dve}(G-e)-1+1 \le \gamma _{dve}(G-e)$. Now assume that u is not a pendant vertex in $G-e$. To dominate the edges incident with u and v twice, a neighbor of u and v, say a, b should be in $D'$. These two vertices a and b dominate the edge e in G. Hence $D'$ is a DVEDS of the graph G. We get $\gamma _{dve}(G) \le \left| D'\right| \le \gamma _{dve}(G-e)$. This gives $\gamma _{dve}(G)-1 \le \gamma _{dve}(G-e) - 1 < \gamma _{dve}(G-e)$. Thus $\gamma _{dve}(G) -1 \le \gamma _{dve}(G-e) \le \gamma _{dve}(G)+2$. $\ \Box$

Let $e \in E(\overline{G})$. Then $G+e$ denotes the graph obtained by adding the edge e.

FormalPara Theorem 1.2

For every graph G and any edge $e \in E(\overline{G})$ we have $\gamma _{dve}(G)-1 \le \gamma _{dve}(G+e) \le \gamma _{dve}(G)$.

FormalPara Proof

We first prove that $\gamma _{dve}(G+e) \le \gamma _{dve}(G)$ for any edge $e=uv\in E(\overline{G})$. Let D be a minimum DVEDS of G. We consider the following cases.

FormalPara Case 1

Assume that $u,v \in D$. Then D is a DVEDS of the graph $G+e$ as the vertices u and v together dominates the edge e. Thus $\gamma _{dve}(G+e) \le \left| D\right| \le \gamma _{dve}(G)$.

FormalPara Case 2

Now let $\left| \{u,v\} \cap D\right| =1$. Without loss of generality assume that $u \in D$. Then the vertex u dominates the edges incident to it. Suppose that to dominate the edges incident with v, a neighbor of v, say a is in D. Thus D is also a DVEDS of the graph $G+e$ as the vertex a dominates the edge uv in $G+e$. We get $\gamma _{dve}(G+e) \le \left| D\right| \le \gamma _{dve}(G)$.

FormalPara Case 3

Now assume that both $u,v \notin D$. If the neighbor of u and v, say a, b are in D, then D is a DVEDS of the graph $G+e$. Thus $\gamma _{dve}(G+e) \le \left| D\right| \le \gamma _{dve}(G)$.

We now prove that $\gamma _{dve}(G)-1 \le \gamma _{dve}(G+e)$. Let $D'$ be a minimum DVEDS of the graph $G+e$, where $e=uv \in E(\overline{G})$. Let us first assume that both $u,v \in D'$. Then $D'$ is a DVEDS of the graph G. Thus $\gamma _{dve}(G)-1 \le \left| D'\right| -1 \le \gamma _{dve}(G+e) - 1 < \gamma _{dve}(G+e)$.

Now assume that $\left| \{u,v\} \cap D'\right| =1$. Without loss of generality assume $u \in D'$. To dominate the edge uv, a neighbor of v, say $a \in D'$. Thus $D'\cup \{a\}$ is a DVEDS of the graph G. Thus $\gamma _{dve}(G) \le \left| D'\right| +1 \le \gamma _{dve}(G+e) +1$. We have $\gamma _{dve}(G)-1 \le \gamma _{dve}(G+e)-1+1 \le \gamma _{dve}(G+e)$.

Now when both $u,v \notin D'$ then it is obvious that $D'$ is itself a DVEDS of the graph G. We get $\gamma _{dve}(G)-1 \le \left| D'\right| -1 \le \gamma _{dve}(G+e)-1 < \gamma _{dve}(G+e)$. $\ \Box$

The subdivision of some edge $e=uv$ in a graph G yields a graph containing one new vertex w, and with an edge set replacing e by two new edges with endpoints uw and wv.

Let us denote by $G_{uv}\oplus w$ the graph obtained from a graph G by subdivision of an edge uv in a graph G.

FormalPara Theorem 1.3

For every graph G and any edge $e=uv$ of G we have $\gamma _{dve}(G) \le \gamma _{dve}(G_{uv}\oplus w) \le \gamma _{dve}(G)+1$.

FormalPara Proof

We first prove that $\gamma _{dve}(G_{uv}\oplus w) \le \gamma _{dve}(G)+1$ for any edge $e=uv$ which is subdivided by a new vertex w with the edge set $\{uw,wv\}$ replacing e. Let D be a minimum DVEDS of G. We consider three cases.

FormalPara Case 1

Assume that $u,v \in D$. Then D is a DVEDS of the graph $G_{uv}\oplus w$, since u and v dominates the edges incident to them and also the edges incident to a vertex adjacent to them. Thus the edges uw and wv of $G_{uv}\oplus w$ are dominated by the vertices u, v. We get $\gamma _{dve}(G_{uv}\oplus w) \le \left| D\right| \le \gamma _{dve}(G) < \gamma _{dve}(G)+1$.

FormalPara Case 2

Now let $\left| \{u,v\} \cap D\right| =1$. Without loss of generality assume that $u \in D$. Then u dominates the edges uw, wv in $G_{uv}\oplus w$. To dominate the edges incident with v, the neighbor of v other than u, say a is in D. It is clear that $D \cup \{v\}$ is a DVEDS of the graph $G_{uv}\oplus w$. We get $\gamma _{dve}(G_{uv}\oplus w) \le \left| D\right| +1 \le \gamma _{dve}(G)+1$.

FormalPara Case 3

Now let both $u,v \notin D$. The edges incident with u are dominated by a neighbor of u, say a other than v and the edges incident with v are dominated by a neighbor of v, say b other than u. It is clear that $D \cup \{u\}$ is a DVEDS of the graph $G_{uv}\oplus w$. Thus $\gamma _{dve}(G_{uv}\oplus w) \le \left| D\right| +1 \le \gamma _{dve}(G) +1$.

We now prove that $\gamma _{dve}(G) \le \gamma _{dve}(G_{uv}\oplus w)$. Let $D'$ be a minimum DVEDS of the graph $G_{uv}\oplus w$. Let us first assume that both $u,v \in D'$. Then $D'$ is a DVEDS of the graph G as u, v dominates the edge uv of G. We have $\gamma _{dve}(G) \le \left| D'\right| \le \gamma _{dve}(G_{uv}\oplus w)$.

Now assume that $\left| \{u,v\} \cap D'\right| =1$. Without loss of generality assume $u \in D'$. To dominate the edges incident with v other than wv, a neighbor of v, say a, other than w is in $D'$. It is clear that $D'$ is a DVEDS of the graph G. We have $\gamma _{dve}(G) \le \left| D'\right| \le \gamma _{dve}(G_{uv}\oplus w)$.

Now assume that both $u,v \notin D'$. To dominate the edges incident with u, a neighbor of u, say a, other than w is in $D'$ and to dominate the edges incident with v, a neighbor of v, say b, other than w is in $D'$. To dominate the edges incident with u and v twice, the vertex $w \in D'$. It is clear that $D' {\setminus} \{w\}$ is a DVEDS of the graph G. We get $\gamma _{dve}(G) \le \left| D'\right| -1 \le \gamma _{dve}(G_{uv}\oplus w) -1 < \gamma _{dve}(G_{uv}\oplus w)$.