# Further Results on Total Edge-Vertex Domination

Authors: Abdulgani Şahin
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Total edge-vertex domination is a new total domination-type parameter. In this paper, the author shows that determining the total edge-vertex domination number in bipartite planar graphs is NP-complete. Also, the author obtains a structural relation between total domination number and total edge-vertex domination number and characterizes the trees whose total edge-vertex domination number is equal to total domination number.


---

## Body

## 1. Introduction

Graphs are indispensable tools in every phase of human daily life and in many disciplines where mathematics permeates [1–3]. Graph theory also has its own invariants. The concept of domination is one of the main parameters in graph theory. The domination is used in the solution of many problems and analysis of events in the historical process of human life. It is also used in solving network problems. Until now, many types of domination have been defined. A study on the total variations of two of these important domination types is conducted here. Their relationship with each other is examined in this study.A graph is usually demonstrated by the symbolG=V,E in which vertices are shown with V and edges are shown with E. Here, we can express two important definitions as follows: the set NGv=u|uv∈E is the open neighborhood of a vertex v in a graph G. The set NGv=NGv∪v is the closed neighborhood of v.The symboldGv indicates the degree of a vertex v∈V and it is the number of vertices adjacent to v. A vertex with degree one is named a last vertex. If a vertex has degree at least two, it is called an internal vertex. A vertex adjacent to a last vertex is called the remote. There are two types of the remote vertices. Provided that a remote vertex is adjacent to a last vertex, it is called a weak remote and provided that a remote vertex is adjacent to at least two last vertices, it is called a strong remote. An edge of the graph G which is incident to a last vertex is called an end edge. The edge adjacent to an end edge (dissimilar from an end edge) is called a remote edge. The distance du,v between any two vertices u and v is the minimum of the lengths of paths between u and v. The diameter of a graph is defined as maxdu,v. The eccentricity is specified as the maximum distance of one vertex from other vertex. If a tree has a even diameter, the middle vertex of the tree is called a central vertex. A path and a tree are indicated by the symbols Pn and T, respectively. The diameter of a tree T is indicated by diamT. Provided that there is an edge e∈ET such that e is an edge containing v as an endpoint, any vertex v of the tree is adjacent to a Pn.LetB be a subset of vertices set of the graph G. The subset B is a dominating set (simply, DS), provided that every vertex in G either is an element of B or is adjacent to at least one vertex in B. The symbol γG indicates the domination number of a graph G and γG is equal to the minimum cardinality of a DS in G. Similarly, a subset B⊆V is a total dominating set (simply, TDS), provided that every vertex of V has a neighbor in B. The symbol γtG indicates the total domination number of a graph G and γtG is equal to the minimum cardinality of a TDS in G [4–7]. We refer to the book [8] for more details about domination theory.An edgeeev-dominates a vertex v provided that e is incident to v or e is incident to a vertex which is adjacent to v. A subset B⊆E is an edge-vertex dominating set (simply, EVDS) of G, provided that every vertex of a graph G is ev-dominated by at least one edge in B. The minimum cardinality of an EVDS is the ev-domination number and denoted by γevG. Peters presented the concept of edge-vertex domination [9]. Lewis made studies that made additional contributions about it [10]. These two studies [11, 12] on the edge-vertex domination number of trees also attract attention.A vertexvve-dominates an edge e which is incident to v and any edge which is adjacent to e. A set B⊆V is a ve-dominating set (simply, VEDS) provided that all edges of a graph G are ve-dominated by at least one vertex in B [9]. The symbol γveG indicates ve-domination number of a graph G and γveG is equal to the minimum cardinality of a VEDS in G.In [13], Boutrig and Chellali presented the total vertex-edge domination. A subset B⊆V is a total vertex-edge dominating set (simply, TVEDS) of G, provided that B is a VEDS and every vertex in B has a neighbor in B [13]. The symbol γvetG indicates the total ve-domination number of a graph G and γvetG is equal to the minimum cardinality of a TVEDS.The total edge-vertex domination was presented in [14]. A subset B⊆E is a total edge-vertex dominating set (simply, TEVDS) of G, provided that B is an EVDS and every edge in B shares an endpoint with another edge in B. The symbol γevtG indicates the total ev-domination number of a graph G and γevtG is equal to the minimum cardinality of a TEVDS. In [14], the authors show that determining the total ev-domination number of bipartite graphs is NP-complete. In this paper, we extend this result to bipartite planar graphs. Moreover, we obtain a relation between total domination number and total ev-domination number and characterize the trees that provide this property.


## 2. Preliminaries

First of all, let us start by stating some basic results that we will use in this study.Observation 1.
Every remote vertex ofG is contained in every TDS of G.Observation 2.
(See [11]). A γevG-set can be determined such that it does not contain any end edge if the diameter of every connected graph G is at least three.Observation 3.
(See [14]). A γevtT-set can be determined such that it does not contain any end edge if the diameter of every tree T is at least four.Observation 4.
(See [14]). Every remote edge is included by a minimum total edge-vertex dominating set if the diameter of every tree is at least four.
Since the graphs with only one edge have no total edge-vertex dominating set, we will not take into account graphs like these ones, by the definition of total domination.Observation 5.
(See [14]). For a nontrivial tree T, γevT≤γevtT.Lemma 1. (See [14]).
For a nontrivial treeT, γevtT≤γtT.


## 3. Complexity Conclusion

The NP-completeness conclusion for the totalev-domination issue in bipartite graphs is here constructed. As stated below, it is shown that TOTAL EV-DOM is NP-complete for bipartite planar graphs and VERTEX COVER is used for this process.


### 3.1. Vertex Cover

#### 3.1.1. Instance

A graphG=V,E and an integer k≤V.


#### 3.1.2. Question

Is there a subsetV′⊆V such that V′≤k and, for each edge uv∈E, at least one of u and v belongs to V′ (i.e., a subset of the vertices of the graph which dominates all of its edges)?Theorem 1.
For bipartite planar graphs, problem TOTAL EV-DOM is NP-Complete.Proof.
Figure1(a) illustrates this proof. Consider an instance graph G of Vertex Cover on a planar graph, a known NP-complete problem [15]. A subdivision graph S1 of G has VS1=VG∪EG and ES1=u,uv,uv,v|uv∈EG, i.e., S1 is obtained from G by replacing its edges by paths of size three. Consider a graph H acquired off the subdivision graph of G by suffixing, for every VG-vertex j in S1 a path of size five with vertices rj, sj, uj, vj, wj and add an edge between uj, the center of the P5, and j. A subdivision S1 of G is a bipartite graph, since we double the size of any cycle of G. Moreover, if G was planar, S1 remains planar with the same planar representation and the addition of the P5 with center adjacent to each VG-vertex of S1 clearly maintain the graph both bipartite and planar.
We claim thatG is of a vertex cover set V′ with V′≤k if and only if H is of a total edge-vertex dominating set D with D≤2VG+k.
LetV′ be a vertex cover set of G with size k. Consider the set S of edges of H composed by the edges siui,uivi|i∈VG∪iui|i∈V. S is composed of triples of edges connected to a central vertex ui. Clearly, all P5’s vertices and all VG-vertices of H are dominated by the edges siui,uivi|i∈V. Moreover, since S is a vertex cover set of G, all EG-vertices of H are dominated by the edges iui|i∈V. Therefore, S is a TEVDS set with size 2VG+k.
Conversely, consider aTEVDS of H with size 2VG+k. We need the edges siui,uivi|v∈VG in S to dominate the vertices ri and wi for every i∈VG. Consequently, S has 2VG such edges and another k edges remain. Provided that there exists an edge between a VG-vertex p and EG-vertex pq of H, since all VG-vertices are dominated by the already 2VG chosen edges, we can pick another total edge-vertex dominating set S′ of same size by replacing this edge by the edge pup. Now the set of edges S′/siui,uivi|v∈VG has size k with edges of the type pup. Since S′ is a total edge-vertex dominating set, these edges dominate all EG-vertices of H and, therefore, a set V′=p|pup∈S′ is a vertex cover set of G with size k. □
Note that we could also relate the domination (and edge domination) problem of a graphG with total ev-dom of a variation of the graph H, if we consider the upper and lower vertices of H as vertices (edges) and there exists an edge among two vertices of H provided that the upper vertex dominates the lower vertex, as described in Figure 1(b) and 1(c)). The same reasoning also applies for an ev-edge dominating set and ve-dominating set, just consider the edges between the upper and lower part of the graph if the upper element dominates the lower element.Figure 1
Planar graphs used for Theorem1.
(a)(b)(c)


## 3.1. Vertex Cover

### 3.1.1. Instance

A graphG=V,E and an integer k≤V.


### 3.1.2. Question

Is there a subsetV′⊆V such that V′≤k and, for each edge uv∈E, at least one of u and v belongs to V′ (i.e., a subset of the vertices of the graph which dominates all of its edges)?Theorem 1.
For bipartite planar graphs, problem TOTAL EV-DOM is NP-Complete.Proof.
Figure1(a) illustrates this proof. Consider an instance graph G of Vertex Cover on a planar graph, a known NP-complete problem [15]. A subdivision graph S1 of G has VS1=VG∪EG and ES1=u,uv,uv,v|uv∈EG, i.e., S1 is obtained from G by replacing its edges by paths of size three. Consider a graph H acquired off the subdivision graph of G by suffixing, for every VG-vertex j in S1 a path of size five with vertices rj, sj, uj, vj, wj and add an edge between uj, the center of the P5, and j. A subdivision S1 of G is a bipartite graph, since we double the size of any cycle of G. Moreover, if G was planar, S1 remains planar with the same planar representation and the addition of the P5 with center adjacent to each VG-vertex of S1 clearly maintain the graph both bipartite and planar.
We claim thatG is of a vertex cover set V′ with V′≤k if and only if H is of a total edge-vertex dominating set D with D≤2VG+k.
LetV′ be a vertex cover set of G with size k. Consider the set S of edges of H composed by the edges siui,uivi|i∈VG∪iui|i∈V. S is composed of triples of edges connected to a central vertex ui. Clearly, all P5’s vertices and all VG-vertices of H are dominated by the edges siui,uivi|i∈V. Moreover, since S is a vertex cover set of G, all EG-vertices of H are dominated by the edges iui|i∈V. Therefore, S is a TEVDS set with size 2VG+k.
Conversely, consider aTEVDS of H with size 2VG+k. We need the edges siui,uivi|v∈VG in S to dominate the vertices ri and wi for every i∈VG. Consequently, S has 2VG such edges and another k edges remain. Provided that there exists an edge between a VG-vertex p and EG-vertex pq of H, since all VG-vertices are dominated by the already 2VG chosen edges, we can pick another total edge-vertex dominating set S′ of same size by replacing this edge by the edge pup. Now the set of edges S′/siui,uivi|v∈VG has size k with edges of the type pup. Since S′ is a total edge-vertex dominating set, these edges dominate all EG-vertices of H and, therefore, a set V′=p|pup∈S′ is a vertex cover set of G with size k. □
Note that we could also relate the domination (and edge domination) problem of a graphG with total ev-dom of a variation of the graph H, if we consider the upper and lower vertices of H as vertices (edges) and there exists an edge among two vertices of H provided that the upper vertex dominates the lower vertex, as described in Figure 1(b) and 1(c)). The same reasoning also applies for an ev-edge dominating set and ve-dominating set, just consider the edges between the upper and lower part of the graph if the upper element dominates the lower element.Figure 1
Planar graphs used for Theorem1.
(a)(b)(c)


## 3.1.1. Instance

A graphG=V,E and an integer k≤V.


## 3.1.2. Question

Is there a subsetV′⊆V such that V′≤k and, for each edge uv∈E, at least one of u and v belongs to V′ (i.e., a subset of the vertices of the graph which dominates all of its edges)?Theorem 1.
For bipartite planar graphs, problem TOTAL EV-DOM is NP-Complete.Proof.
Figure1(a) illustrates this proof. Consider an instance graph G of Vertex Cover on a planar graph, a known NP-complete problem [15]. A subdivision graph S1 of G has VS1=VG∪EG and ES1=u,uv,uv,v|uv∈EG, i.e., S1 is obtained from G by replacing its edges by paths of size three. Consider a graph H acquired off the subdivision graph of G by suffixing, for every VG-vertex j in S1 a path of size five with vertices rj, sj, uj, vj, wj and add an edge between uj, the center of the P5, and j. A subdivision S1 of G is a bipartite graph, since we double the size of any cycle of G. Moreover, if G was planar, S1 remains planar with the same planar representation and the addition of the P5 with center adjacent to each VG-vertex of S1 clearly maintain the graph both bipartite and planar.
We claim thatG is of a vertex cover set V′ with V′≤k if and only if H is of a total edge-vertex dominating set D with D≤2VG+k.
LetV′ be a vertex cover set of G with size k. Consider the set S of edges of H composed by the edges siui,uivi|i∈VG∪iui|i∈V. S is composed of triples of edges connected to a central vertex ui. Clearly, all P5’s vertices and all VG-vertices of H are dominated by the edges siui,uivi|i∈V. Moreover, since S is a vertex cover set of G, all EG-vertices of H are dominated by the edges iui|i∈V. Therefore, S is a TEVDS set with size 2VG+k.
Conversely, consider aTEVDS of H with size 2VG+k. We need the edges siui,uivi|v∈VG in S to dominate the vertices ri and wi for every i∈VG. Consequently, S has 2VG such edges and another k edges remain. Provided that there exists an edge between a VG-vertex p and EG-vertex pq of H, since all VG-vertices are dominated by the already 2VG chosen edges, we can pick another total edge-vertex dominating set S′ of same size by replacing this edge by the edge pup. Now the set of edges S′/siui,uivi|v∈VG has size k with edges of the type pup. Since S′ is a total edge-vertex dominating set, these edges dominate all EG-vertices of H and, therefore, a set V′=p|pup∈S′ is a vertex cover set of G with size k. □
Note that we could also relate the domination (and edge domination) problem of a graphG with total ev-dom of a variation of the graph H, if we consider the upper and lower vertices of H as vertices (edges) and there exists an edge among two vertices of H provided that the upper vertex dominates the lower vertex, as described in Figure 1(b) and 1(c)). The same reasoning also applies for an ev-edge dominating set and ve-dominating set, just consider the edges between the upper and lower part of the graph if the upper element dominates the lower element.Figure 1
Planar graphs used for Theorem1.
(a)(b)(c)


## 4. Totalev-Dominating Number and Total Dominating Number

Note that the edges of a minimumTEVDS of a graph G do not form cycles on the graph. Otherwise, we could remove one of these edges of the cycle and we would still get a TEVDS of smaller size. Therefore, the edges of a minimum TEVDS of G form a forest subgraph of G.Assume thatS is a minimum TEVDS and let T1,…,Tp be the p trees of the forest given by the edges of S. We have that the ∪1≤i≤pETi+p vertices of these p trees are a TDS of G. Therefore, γtG≤γevtG+p, i.e., γevtG≥γtG−p.Consider a minimumTDS, which is shown by B, of G with size γtG. Let T1,T2,…,Tq be a forest between vertices of B. If all trees have three or more vertices, then the edges of these trees are a TEVDS, which is shown by S, of G. This holds due to the definition of “total”. Otherwise, we need to add an additional edge to the trees with two vertices to it be a TEVDS. For each tree Ti with VTi=2 vertices in B, we include two edges in S. And for each tree Ti with VTi≥3 vertices in B, we include VTi−1 edges of the tree in S. Therefore, γevtG≤γtG and the upper bound is tight only when all trees T1,T2,…,Tq have two vertices. Otherwise, for each tree with three or more vertices, we increase the gap between γevtG and γtG by one unit. I.e., if there are x of such trees with size three or more, then γevtG+x≤γtG.Consider now a minimumTEVDS of G. It would be seen as the minimum value of S−u among whole the total dominating sets S of G (each TDS has a value u given with the maximum number of trees with three vertices or more connecting the vertices of S). In the worst case scenario when u=0, all trees connecting the vertices of S have two vertices and we have γevtG=S. Otherwise, each tree with three or more vertices connecting the vertices of S increase the value of u in one unit. Since u is upper bounded by S/3 (each unit of u correspond a tree with at least three vertices of S), we have min2S/3≤minS−u=γevtG. And since γtG≤S, we have 2γtG/3≤γevtG.Therefore,2γtG/3≤γevtG≤γtG. This information is interesting for the following reasons. Since it is hard to approximate γtG [16], it will be also hard to approximate the value of γevtG.Now, we qualify whole trees on the equalityγtT=γevtT. We will use a family ℱ of trees T=Tq. Suppose that T1=P3,P4,P7,P8,P12 and for a q∈ℤ+, Tq+1 is a tree repetitively acquired over Tq per one of the three processes mentioned below:ProcessO1: suffix a vertex by joining it to any remote vertex of Tq or an internal vertex adjacent to a remote vertex.ProcessO2: suffix a path P3 by joining one of its last vertices to a vertex of Tq which is adjacent to a path P3.ProcessO3: suffix a path P4 by joining one of its last vertices to an internal vertex of Tq for which is not a remote vertex.We can give an example of the implementation of these processes as shown in Figure2.Figure 2
A treeT∈ℱ which is obtained from T1:xyztuvw, by adding the vertices y1, z1, u1, v1 with Process O1, by adding the path P3:prs, with Process O2 and by adding the paths P4:abcd,klmn,efgh, with Process O3 such thatγtT=γevtT=12.There is an exceptional situation in the familyℱ because of the structure of the tree P4. P4 is the only path which has two adjacent remote vertices and has not an internal vertex other than these remote vertices. Thus, if a path P4 is attached by joining one of its last vertices to a remote vertex of R′=T1=P4, it is found as γtT=γevtT and T∈ℱ. The two examples of trees for the exceptional situation are depicted in Figure 3.Figure 3
The two exceptional treesH1, H2 obtained from T1=P4 such that γtH1=γevtH1=4 and γtH2=γevtH2=6.Theorem 2.
LetT be a tree. If T∈ℱ, then γtT=γevtT.Proof.
The induction is operated over the numberq of processes used to build the tree T=Tq+1. Provided that T=T1∈P3,P4,P7,P8,P12, then γtP3=2=γevtP3, γtP4=2=γevtP4, γtP7=4=γevtP7, γtP8=4=γevtP8, and γtP12=6=γevtP12. Then, suppose that the equality is achieved provided each R′=Tq that is a component of ℱ acquired through q−1 processes.
First suppose thatT=Tq+1 is gotten over R′ through Process O1. Assume that a is a vertex suffixed to a remote vertex or an internal vertex h of R′ which is adjacent to a remote vertex. Let B′ is a TDS of R′. B′ is also a TDS of T by Observation 1. Thus, we have γtT≤γtR′. Moreover, we know that γevtR′≤γevtT. So, γtT≤γtR′=γevtR′≤γevtT. By Lemma 1γevtT≤γtT. As a result, γevtT=γtT.
Suppose thatT=Tq+1 is gotten over R′ per Process O2. Now we assume that Process O2 is applied a vertex h that is adjacent to a path P3xyz. Let abc is suffixed by joining a to h. Let B′ be a γtR′-set. z and c are dominated. Then, the remote vertices b, y and the neighbors of these remote vertices a, x are included by a γtT-set. Consequently, B′∪a,b is a γtT-set and γtT≤γtR′+2. Also, to ev-dominate the vertices c and z, the edges ab, xy and the neighbors of these edges ha, hx are included by a γevtT-set. In this way, provided that B is a γevtT-set, B/ha,ab is a γevtR′-set. We get that γevtT≥γevtR′+2. Consequently, γtT≤γtR′+2=γevtR′+2≤γevtT−2+2=γevtT. From the result and Lemma 1, we obtain that γevtT=γtT.
Suppose thatT=Tq+1 is acquired over R′ per Process O3. We assume a path P4abcl is suffixed by joining a to an internal vertex x of T=Tq that is not a last vertex. Consider that B′ be a γtR′-set. To dominate l, the remote vertex c and its neighbor b are included by a γtT-set. So, B′∪b,c is a γtT-set and γtT≤γtR′+2. Also, to ev-dominate the vertex l, the edge bc and its neighbor ab are included by a γevtT-set. So, provided that B is a γevtT-set, B∖ab,bc is a γevtR′-set. We obtain that γevtT≥γevtR′+2. Consequently, γtT≤γtR′+2=γevtR′+2≤γevtT−2+2=γevtT. From Lemma 1, we obtain that γevtT=γtT.Theorem 3.
LetT be a tree. If γevtT=γtT, then T∈ℱ.Proof.
There is noTEVDS in a graph that possesses a single edge. Thus, we consider trees with at least two edges. If diamT=2, then T is a star. If T=P3, then T∈ℱ. If T is a star different from P3 then it can be obtained from T=T1 by Process O1. Therefore, T∈ℱ. Now, assume that diamT is at least three and the result is true for each tree R′=Tq with order 4≤n′<n.
First assume some remote vertex ofT, for example x, is strong. Let y be a last vertex adjacent to x and R′=T−y. Let B′ be a γevtR′-set. By Observation 3, a γevtT-set can be determined such that it does not contain any end edge. So, B′ is a γevtT-set and γevtT≤γevtR′. Consequently, γtR′≤γtT. We have γtR′≤γtT=γevtT≤γevtR′. From Lemma 1, γevtR′≤γtR′. Thus, we obtain that γevtR′=γtR′. According to the inductive hypothesis, we obtain that R′∈ℱ and T can be obtained from R′ by Process O1. Thus, from now on, we assume that every remote vertex of T is weak.
Now, we rootT at a vertex r of maximum eccentricity diamT. Consider that t is a last vertex at maximum distance from r, v is parent of t, h is parent of v, g is parent of h, provided that diamT≥5, l is parent of g and provided that diamT≥6, e is parent of l in the rooted tree. The symbol Tx indicates the subtree induced by a vertex x and its descendants in the rooted tree T. Assume that B is a γevtT-set. B′ is a γevtR′-set. Likewise, let S be a γtT-set, S′ is a γtR′-set.Case 1.
We observed the situations overv. Let dTv be equal to 2. Due to the choice of the diametrical path, h is of a remote vertex else v or h has a last vertex.Subcase 1.1.
Assume that some child ofh is a last vertex and it is indicated by x. As a result, it is found that h is a remote vertex. Let R′=T−x. From Observation 3, there exists a γevtT-set that includes no end edge. Thus, the vertex x is ev-dominated by hv and γevtT≤γevtR′. Furthermore, the vertices h and v are included by every γtT-set according to Observation 1. Thus, γtR′≤γtT. Therefore, γtR′≤γtT=γevtT≤γevtR′ and by Lemma 1, γevtR′≤γtR′. Consequently, we obtain that γevtR′=γtR′. According to the inductive hypothesis, we obtain that R′∈ℱ and T can be obtained over R′ by Process O1.Subcase 1.2.
Suppose that within the children ofh there exists a remote vertex x, else v. Assume that R′=T−Tv. By Observation 4 the edges hv, hx are included by a minimum TEVDS of T. Thus, B′∪hv is a γevtT-set. In this case, B′ is not a TEVDS but the edge hx has not a neighbor in B′ for this situation. In order to attain the totality of B′, the edge gh has to be included by B′. So, B/hv∪gh is a γevtR′-set and γevtR′=γevtT. Moreover, the vertices h, v, x are included by S. Then, S/v is a γtR′-set, we obtain that γtT≥γtR′+1. Consequently, γtR′≤γtT−1=γevtT−1=γevtR′−1<γevtR′.Case 2.
LetdTh be equal to 2. Due to the choice of the diametrical path, g is of a child else h, e.g., x such that the distance of g to the farthest vertex of Tx is one or two or three.Subcase 2.1.
Suppose that some child ofg is a last vertex and it is shown by x. Consider that R′=T−x. From Observation 3, a γevtT-set can be determined such that it does not contain any end edge. Thus, the vertex x is ev-dominated by lg and γevtT≤γevtR′. Furthermore, to dominate x, the vertex g is included by every γtT-set. So, S′=S−g is a γtR′-set, γtR′≤γtT−1. Therefore, γtR′≤γtT−1=γevtT−1≤γevtR′−1<γevtR′.Subcase 2.2.
A remote vertexx can be determined within the children of g, where Tx:xy. Consider that R′=T−Tg. To ev-dominate the vertices y, t the edges gx, gh and hv are included by a minimal TEVDS of T. So, B′∪gx,gh,hv is a γevtT-set. γevtT≤γevtR′+3. Moreover, the remote vertices x, v and their neighbors g, h are included by S. So, S/x,g,h,v is a γtR′-set, we obtain that γtT≥γtR′+4. Therefore, γtR′≤γtT−4=γevtT−4=γevtR′+3−4<γevtR′.Subcase 2.3.
A vertexx can be determined within the children of g, where Tx:xyz. Consider that R′=T−Th. So, B′∪gh,hv is a γevtT-set. γevtT≤γevtR′+2. Also, S/h,v is a γtR′-set and γtT≥γtR′+2. Then, γtR′≤γtT−2=γevtT−2≤γevtR′+2−2=γevtR′. From Lemma 1, we obtain that γtR′=γevtR′ and according to the inductive hypothesis, R′∈ℱ and T is acquired off R′ per Process O2.Case 3.
LetdTg be equal to 2. Due to the choice of the diametrical path, l is of a child else g, e.g., x such that the distance of l to the farthest vertex of Tx is one or two or three or four.Subcase 3.1.
Consider that some child ofl is a last vertex. It is shown by x. Consider that R′=T−Tg. In order to ev-dominate the vertices x and t, the edges lg, gh, hv are included by a γevtT-set. We obtain that B′∪lg,gh,hv is a γevtT-set and γevtT≤γevtR′+3. Furthermore, to dominate x and t, the remote vertices l, v and their neighbors g, h are included by every γtR′-set. So, S′=S−l,g,h,v is a γtR′-set. γtR′≤γtT−4. Therefore, γtR′≤γtT−4=γevtT−4≤γevtR′+3−4<γevtR′.
IfR′=P4, then there exists an exceptional situation in here. Since P4 do not contain internal vertices out of remote vertices, after a path P4 is attached to R′=P4 we obtain that γtT=γevtT=4 and T∈ℱ.Subcase 3.2.
A remote vertexx can be determined among the children of l, where Tx:xy. Consider that R′=T−Tg. To ev-dominate the vertices y, t, the edges lx, hv and their neighbors el, gh are included by a minimal TEVDS of T. Then, B′∪gh,hv is a γevtT-set and γevtT≤γevtR′+2. Hence, to dominate the last vertices y, t, the remote vertices x, v and their neighbors l, h are included by S. Consequently, S/h,v is a γtR′-set, we obtain γtT≥γtR′+2. So, γtR′≤γtT−2=γevtT−2=γevtR′+2−2≤γevtR′. According to the inductive hypothesis, we obtain that R′∈ℱ and T can be obtained from R′ by Process O3.Subcase 3.3.
A vertexx can be determined within the children of l, where Tx:xyz. Consider that R′=T−Tg. To ev-dominate the vertices z, t, the remote edges xy, hv and their neighbors lx, gh are included by a minimal TEVDS of T. So B′∪gh,hv is a γevtT-set and γevtT≤γevtR′+2. To dominate the last vertices z, t, the remote vertices y, v and their neighbors x, h are included by S. Consequently, S/h,v is a γtR′-set. We obtain γtT≥γtR′+2. Then, γtR′≤γtT−2=γevtT−2=γevtR′+2−2≤γevtR′. Per Lemma 1, we obtain that γevtR′=γtR′ and according to the inductive hypothesis, we obtain that R′∈ℱ and T can be obtained from R′ by Process O3.Subcase 3.4.
A vertexx can be determined among the children of l, where Tx:xyzs. Consider that R′=T−Tg. To ev-dominate the vertices s, t, the remote edges yz, hv and their neighbors xy, gh are included by a minimal TEVDS of T. So B′∪gh,hv is a γevtT-set and γevtT≤γevtR′+2. To dominate the last vertices s, t, the remote vertices z, v and their neighbors y, h are included by S. Consequently, S/h,v is a γtR′-set. We obtain γtT≥γtR′+2. Hence, γtR′≤γtT−2=γevtT−2=γevtR′+2−2≤γevtR′. From Lemma 1, we obtain that γevtR′=γtR′ and according to the inductive hypothesis, we obtain that R′∈ℱ and T can be obtained from R′ by Process O3.Case 4.
LetdTl be equal to 2. We obtain that T=P6∉ℱ provided that dTe=1. Now assume that dTe≥3. Let R′=T−Tl. In this case, B′∪gh,hv is a γevtT-set. We have γevtT≤γevtR′+2. On the other hand, g, h, v are contained in a TDS of T. Finally, S′=S/g,h,v is a γtR′-set. γtR′+3≤γtT. Thus, γtR′≤γtT−3=γevtT−3≤γevtR′+2−3<γevtR′.



---

*Source: 5439610-2022-03-21.xml*