A vertex v of a graph Gve-dominates every edge incident with a vertex in its closed neighborhood NG[v]. A set of vertices is a vertex-edge dominating set (ve-dominating set) if every edge of G is ve-dominated by some vertex in the set. The minimum cardinality of such a set is the vertex-edge domination number γve(G), also known as the isolation number. In this paper, we study the effect of vertex removal on γve(G), establish sharp bounds on γve(G−v) and characterize the vertices whose removal decreases, preserves, or increases γve(G). Let V0(G) and V+(G) denote the sets of vertices whose removal preserves and increases γve(G), respectively, and let Vfix0(G) consist of the vertices in V0(G) belonging to every minimum ve-dominating set. We prove that ∣V0(G)∣≥3∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1). In particular, ∣V0(G)∣≥2∣V+(G)∣. We also prove that every vertex in Vfix0(G) lies on a cycle and that V0(T)=∅ for every tree T of order at least three.
Introduction
All graphs considered in this paper are finite, simple, and undirected. For a graph G, let V(G) and E(G) denote its vertex set and edge set, respectively. The open neighborhood of a vertex v is NG(v)={u∈V(G):uv∈E(G)}, and its closed neighborhood is NG[v]=NG(v)∪{v}. The degree of v is d(v)=∣NG(v)∣. A vertex v is called an isolated vertex if d(v)=0. If d(v)=1, then v is called a leaf. For S⊆V(G), let NG(S)=⋃v∈SNG(v) and NG[S]=NG(S)∪S. Note that NG(S) may contain vertices of S. We omit the subscript G when the graph is clear from the context.
For any S⊆V(G), let G[S] denote the subgraph induced by S, and write G−S=G[V(G)∖S]. We abbreviate G−{v} to G−v. A set S is independent if G[S] is edgeless. For E′⊆E(G), let G[E′] denote the edge subgraph with edge set E′ and vertex set consisting of the endvertices of edges in E′. The path, cycle, and star of order n are denoted by Pn, Cn, and K1,n−1, respectively; 2K2 denotes the disjoint union of two edges. A forest is a graph containing no cycle, and a tree is a connected forest. The distanced(u,v) between two vertices u and v in a graph G is the length of a shortest path in G which connects u and v, and d(u,v)=∞ when u and v belong to distinct components.
For any vertex v in a graph G, we say that vve-dominates every edge in G which is incident with some vertex in N[v]. A subset S⊆V(G) is a vertex-edge dominating set of G, abbreviated ve-dominating set, if every edge e in G is ve-dominated by some vertex v in S. The vertex-edge domination number, abbreviated ve-domination number, of G is the minimum cardinality of a ve-dominating set of G, denoted by γve(G). We call a ve-dominating set of cardinality γve(G) a γve(G)-set. Equivalently, S is a ve-dominating set if and only if G−N[S] is edgeless. Thus, γve(G) equals the isolation number ι(G) studied by Caro and Hansberg [3]. When G is edgeless or G has no vertices, γve(G)=0. The parameter is additive over components, since each component must be ve-dominated independently. In particular, removing an isolated vertex does not change γve(G).
Vertex-edge domination was introduced by Peters [10] and further studied by Lewis [7] and Lewis et al. [8]. The same parameter was investigated by Caro and Hansberg [3] under the name of the isolation number. Bounds and structural properties of vertex-edge domination have been established for general graphs and trees [2, 5, 6, 14]. Algorithmic aspects have also been studied for various graph classes, including cubic graphs and unit disk graphs [4, 9, 13].
The structure of minimum ve-dominating sets and the effects of graph modifications have also been studied. Senthilkumar, Chellali, Naresh Kumar and Venkatakrishnan [11] studied graphs with a unique minimum ve-dominating set and gave characterizations of the trees with this property. More recently, Bartolo, Borg, Dettlaff, Lemańska and Zyliński [1] investigated isolation criticality under multiple edge subdivision. In a related direction, Thakkar and Jamvecha [12, Section 1, p. 245 studied vertex removal under a different stated definition: v dominates xy when {x,y}⊆N[v]. Our definition requires only {x,y}∩N[v]=∅. In this paper, we study the effect of vertex removal on γve(G) by examining the structure of γve(G)-sets.
Removing a vertex may decrease, preserve, or increase the ve-domination number. Accordingly, we partition V(G) into the following three classes:
V−(G)={v∈V(G):γve(G−v)<γve(G)},
V0(G)={v∈V(G):γve(G−v)=γve(G)},
V+(G)={v∈V(G):γve(G−v)>γve(G)}.
Let CVRve denote the class of vertex-edge domination vertex-critical graphs, or γve-vertex-critical graphs for short, consisting of all graphs G satisfying γve(G)=γve(G−v) for every v∈V(G). Thus G∈CVRve if and only if V0(G)=∅.
The vertices of G can also be classified in terms of γve(G)-sets as follows. Let S(G) denote the family of all γve(G)-sets, and let S(v,G)={S∈S(G):v∈S}. A vertex v is γve(G)-good if v∈S for some γve(G)-set S, and γve(G)-bad if v∈/S for every γve(G)-set S. It is γve(G)-fixed if v∈S for every γve(G)-set S, and γve(G)-free if v is contained in some γve(G)-set but not in all γve(G)-sets. The corresponding sets are denoted by Vgood(G),Vbad(G),Vfix(G),Vfree(G), respectively. In particular, the fixed, free, and bad vertices form a partition of V(G). We further define
Vfree0(G)=Vfree(G)∩V0(G),
Vfree−(G)=Vfree(G)∩V−(G),
Vfixk(G)={v∈Vfix(G):γve(G−v)=γve(G)+k}(k≥0),
where k is an integer. In particular, Vfix0(G)=Vfix(G)∩V0(G).
By associating pairwise disjoint sets of private-edge endvertices with fixed vertices (Theorem 2.18), we obtain the following weighted bound (Corollary 2.19):
We also prove that every vertex in Vfix0(G) lies on a cycle (Theorem 2.22) and that V0(T)=∅ for every tree T of order at least three (Theorem 2.21).
Section 2 presents the main results and their proofs. Section 3 discusses consequences for vertex-removal critical graphs and questions for further study.
Main results
In this section, we state the main results on the effect of vertex removal on the ve-domination number. We begin with sharp bounds on the ve-domination number after the removal of a vertex.
Theorem 2.1. Let G be a graph and v∈V(G) be a non-isolated vertex. Then
γve(G)−1≤γve(G−v)≤γve(G)+d(v)−1.(1)
The lower bound also holds for isolated vertices. Moreover, the bounds are sharp.
Proof. Let S be a γve(G−v)-set. Then S∪{v} is a ve-dominating set of G. Hence γve(G)≤γve(G−v)+1, that is, γve(G−v)≥γve(G)−1.
Now we prove that γve(G−v)≤γve(G)+d(v)−1. Let S′ be a γve(G)-set. If v∈S′, then (S′∖{v})∪N(v) is a ve-dominating set of G−v, since every edge of G−vve-dominated by v is incident with a vertex of N(v). Therefore, we have γve(G−v)≤γve(G)+d(v)−1.
If v∈/S′, then S′ is also a ve-dominating set of G−v, so γve(G−v)≤γve(G). Hence, we have γve(G−v)≤γve(G)+d(v)−1, where the last inequality follows from d(v)≥1.
For sharpness of the lower bound, let G=K1,k, where k≥1, and let v be its center. Then γve(G)=1 and γve(G−v)=0. For sharpness of the upper bound, let G be obtained from K1,r (r≥1) by subdividing each edge once, and let v be the original center. Then {v}ve-dominates G, while G−v≅rK2. Hence γve(G−v)=r=γve(G)+d(v)−1.
Theorem 2.1 shows that removing a non-isolated vertex v decreases the ve-domination number by at most one, while it may increase the ve-domination number by as much as d(v)−1. Consequently, we have the following.
Corollary 2.2. Let G be a graph and v∈V(G). If v∈V−(G), then γve(G−v)=γve(G)−1. If v∈V+(G), then γve(G−v)=γve(G)+r for some integer r with 1≤r≤d(v)−1.
On vertices in V−(G)
In this subsection, we characterize the vertices in V−(G) in terms of private edges of minimum ve-dominating sets.
Recall that, for S⊆V(G) and v∈S, an edge e∈E(G) is a private edge of v with respect to S if v ve-dominates e and no vertex of S∖{v} does. The set of all such edges is denoted by peG[v,S].
Observation 2.3. Let G be a graph and v∈V−(G). Then for every S∈S(G−v) and every u∈NG[v], S∪{u}∈S(G).
Proof. Let S∈S(G−v) and u∈NG[v]. By Corollary 2.2, ∣S∣=γve(G)−1. The set S ve-dominates every edge of G−v, and u ve-dominates every edge incident with v. Thus S∪{u} is a ve-dominating set of G, and
γve(G)≤∣S∪{u}∣≤∣S∣+1=γve(G).
Hence S∪{u}∈S(G).
The following characterization is the analogue of [12 Theorem 6] for the definition used here. The proof follows the same private-edge argument.
Theorem 2.4. Let G be a graph and v∈V(G). Then v∈V−(G) if and only if there exists a γve(G)-set S with v∈S such that ∅=peG[v,S]⊆{uv:u∈NG(v)}.
Proof. Suppose first that v∈V−(G), and let S′ be a γve(G−v)-set. By Observation 2.3, S=S′∪{v} is a γve(G)-set. If peG[v,S]=∅, then S′ is a ve-dominating set of G, contradicting the assumption that v∈V−(G). Thus, peG[v,S]=∅. Now we prove peG[v,S]⊆{uv:u∈NG(v)}. If there exists some edge e∈peG[v,S] that is not incident with v, then e∈E(G−v) and it is not ve-dominated by any vertex in S′. This contradicts the assumption that S′ is a γve-set of G−v. Hence, peG[v,S]⊆{uv:u∈NG(v)}.
Conversely, suppose that there exists a γve(G)-set S with v∈S such that peG[v,S]=∅ and peG[v,S]⊆{uv:u∈NG(v)}. Then peG[v,S]∩E(G−v)=∅, implying that S∖{v} is a ve-dominating set of G−v. Thus, γve(G−v)≤∣S∣−1=γve(G)−1. Hence v∈V−(G).
The following result is a consequence of Theorem 2.4.
Corollary 2.5. Let G be a graph. Then V(G)=V−(G) if and only if for every v∈V(G), there exists a γve(G)-set S such that v∈S and ∅=peG[v,S]⊆{uv:u∈NG(v)}.
Next, we present several properties of v∈V−(G).
Proposition 2.6. Let G be a graph. Then the following statements hold:
V−(G)=Vfree−(G);
For every v∈V−(G), Vbad(G)∪NG(v)⊆Vbad(G−v);
For every v∈V−(G), Vfix(G)⊆Vfix(G−v).
Proof. (1) Since Vfree−(G)=Vfree(G)∩V−(G), Vfree−(G)⊆V−(G). Conversely, let v∈V−(G) and S′ be a γve(G−v)-set. Since isolated vertices belong to V0(G), we have NG(v)=∅. Then by Observation 2.3, both S′∪{v} and S′∪{u} are γve(G)-sets, where u∈NG(v). Thus, v is γve(G)-free. Hence V−(G)⊆Vfree−(G).
(2) For any u∈NG(v), suppose that u∈/Vbad(G−v). Then there exists a γve(G−v)-set S containing u. Since uve-dominates every edge incident with v, S is also a ve-dominating set of G. Hence γve(G)≤∣S∣=γve(G)−1, a contradiction. Thus NG(v)⊆Vbad(G−v).
Let w∈Vbad(G). If there is a set S∈S(w,G−v), then S∪{v}∈S(w,G). This contradicts w∈Vbad(G). Thus, we have w∈Vbad(G−v). Hence Vbad(G)∪NG(v)⊆Vbad(G−v).
(3) By (1), v∈/Vfix(G). Let v′∈Vfix(G) and S′ be any γve(G−v)-set. By Observation 2.3, S′∪{v} is a γve(G)-set. Since v′=v and v′∈Vfix(G), we have v′∈S′. Thus v′∈Vfix(G−v), and hence Vfix(G)⊆Vfix(G−v).
On vertices in V+(G)
In this subsection, we characterize the vertices v∈V+(G). The following observation follows directly from the definition.
Observation 2.7. Let G be a graph and S∈S(G). Then for every vertex v∈V(G)∖S, S is a ve-dominating set of G−v.
Proposition 2.8. Let G be a graph and v∈V(G). If v∈V+(G), then v∈Vfix(G).
Proof. Let v∈V+(G). Suppose that v∈/Vfix(G). Then there exists a γve(G)-set S with v∈/S. By Observation 2.7, S is also a ve-dominating set of G−v. Thus, γve(G−v)≤∣S∣=γve(G). This contradicts v∈V+(G).
By Proposition 2.8, no free vertex belongs to V+(G). Thus Vfree(G)=Vfree−(G)∪Vfree0(G).
To characterize the vertices in V+(G), we introduce the following exchange parameter. Let S be a γve(G)-set containing the vertex v. For R⊆S∖{v}, define
ρS(v,R)=min{∣X∣:X⊆V(G)∖S and (S∖(R∪{v}))∪Xve-dominates G−v}.
We call ρS(v,R) the exchange number of v with respect to S and R. Every vertex of S has a neighbor outside S; otherwise, it would have no private edge, contradicting the minimality of S. Thus V(G)∖S dominates G−v, so X=V(G)∖S is feasible for every R⊆S∖{v}. Consequently,
0≤ρS(v,R)≤∣V(G)∖S∣.
Lemma 2.9. Let G be a graph, v∈V(G), and S be a γve(G)-set containing v. Then
γve(G−v)=γve(G)−1+R⊆S∖{v}min(ρS(v,R)−∣R∣).
Proof. For any R⊆S∖{v}, let X⊆V(G)∖S be a set of cardinality ρS(v,R) such that D=(S∖(R∪{v}))∪X is a ve-dominating set of G−v. Since X∩S=∅, we have
∣D∣=γve(G)−1−∣R∣+ρS(v,R).
Therefore,
γve(G−v)≤γve(G)−1+R⊆S∖{v}min(ρS(v,R)−∣R∣).(2)
Conversely, let D be a γve(G−v)-set, and let
R=(S∖{v})∖DandX=D∖S.
Then R⊆S∖{v}, X⊆V(G)∖S, and D=(S∖(R∪{v}))∪X. Hence, by the definition of ρS(v,R), ρS(v,R)≤∣X∣.
Theorem 2.10. Let G be a graph and v∈V(G). Then v∈V+(G) if and only if there exists a γve(G)-set S containing v such that ρS(v,R)≥∣R∣+2 for every R⊆S∖{v}.
Proof. Suppose that v∈V+(G), and let S be a γve(G)-set. By Proposition 2.8, v∈S. By Lemma 2.9, we have
R⊆S∖{v}min(ρS(v,R)−∣R∣)=γve(G−v)−γve(G)+1≥2.
Hence ρS(v,R)≥∣R∣+2 for every R⊆S∖{v}.
Conversely, suppose that such a set S exists. By Lemma 2.9,
To further investigate the structure of vertices in V+(G), we first establish the following lemma concerning the vertex-edge domination number.
Lemma 2.11. Let G be a graph. If γve(G)≥2, then G contains either an induced copy of 2K2 or a copy of C5.
Proof. Suppose that γve(G)≥2 and that G contains neither an induced copy of 2K2 nor a copy of C5. Let v be a vertex of maximum degree in G. We claim that {v} is a ve-dominating set of G.
Suppose not. Then G−N[v] contains an edge xy. For every u∈N(v), the edges vu and xy do not induce a 2K2. Since v is adjacent to neither x nor y, the vertex u must be adjacent to at least one of x and y.
Let
A=N(v)∩N(x)andB=N(v)∩N(y).
Then
A∪B=N(v).
If there exist u∈A∖B and z∈B∖A, then v−u−x−y−z−v forms a C5, a contradiction. Hence either A⊆B or B⊆A.
Without loss of generality, suppose that A⊆B. Then B=N(v). Since xy∈E(G) and x∈/N[v], we have
d(y)≥∣N(v)∣+1=d(v)+1,
contradicting the choice of v as a vertex of maximum degree. Therefore, {v} is a ve-dominating set of G, and hence γve(G)=1, a contradiction.
The converse of Lemma 2.11 does not hold in general. For example, take an induced 2K2 and add a vertex adjacent to all four of its vertices. Then this new vertex ve-dominates every edge of the resulting graph.
We now apply Lemma 2.11 to the private edges of a vertex in V+(G).
Theorem 2.12. Let G be a graph and v∈V+(G). For any γve(G)-set S, let U=V(G[peG[v,S]])∖{v}. Then the vertex-induced subgraph G[U] contains either an induced copy of 2K2 or a copy of C5.
Proof. Since v∈V+(G), by Proposition 2.8, we have v∈Vfix(G), and hence v∈S. We claim that γve(G[U])≥2.
If E(G[U])=∅, then every private edge of v with respect to S is incident with v. Thus, S∖{v} is a ve-dominating set of G−v, contradicting v∈V+(G). Hence E(G[U])=∅.
Suppose that γve(G[U])=1, and let x∈U be a ve-dominating vertex of G[U]. Every edge in E(G−v)∖peG[v,S] is ve-dominated by some vertex of S∖{v}, while every edge in peG[v,S]∩E(G−v) belongs to G[U] and is ve-dominated by x. Therefore, (S∖{v})∪{x} is a ve-dominating set of G−v. Consequently,
γve(G−v)≤∣(S∖{v})∪{x}∣≤∣S∣=γve(G),
contradicting v∈V+(G). Thus γve(G[U])≥2. By Lemma 2.11, G[U] contains either an induced 2K2 or a C5.
The next theorem shows that no vertex of V+(G) is adjacent to a vertex of V−(G).
Theorem 2.13. For two vertices u∈V+(G) and v∈V−(G), d(u,v)≥2. Moreover, the bound is sharp.
Proof. Clearly, u and v are not isolated vertices. Suppose that there exist two vertices u∈V+(G) and v∈V−(G) such that d(u,v)<2. Then uv∈E(G). Let Sv be a γve(G−v)-set with cardinality γve(G)−1. We must have u∈Sv; otherwise, Sv∪{v} is a γve(G)-set and u∈/Sv∪{v}. This contradicts u∈V+(G). Since uv∈E(G), u ve-dominates all edges which are incident with v. Thus, Sv is a ve-dominating set of G. This contradicts v∈V−(G). Hence, we have d(u,v)≥2.
To see the sharpness of the bound, consider the graph in Figure 1(a), where γve(G)=2, γve(G−u)=3, and γve(G−v)=1. Thus u∈V+(G), v∈Vfree−(G), and d(u,v)=2.
Figure 1. (a) u∈V+(G) and v∈V−(G) with d(u,v)=2. (b) u,v∈V+(G).
:::
The following is an immediate consequence of Theorem 2.13.
Corollary 2.14. Let G be a graph and v∈V+(G). Then N(v)⊆V+(G)∪V0(G).
The conclusion of Corollary 2.14 cannot be strengthened to N(v)⊆V0(G). Indeed, in the graph G in Figure 1(b), u and v are adjacent and γve(G)=2, whereas γve(G−u)=γve(G−v)=3.
On vertices in V0(G)
We now study vertices whose removal preserves the ve-domination number.
Observation 2.15. Let G be a graph. Then V0(G)=Vfix0(G)∪Vfree0(G)∪Vbad(G).
Proof. By Proposition 2.6(1) and Proposition 2.8, V−(G)⊆Vfree(G) and V+(G)⊆Vfix(G). Hence Vbad(G)⊆V0(G). Intersecting the partition V(G)=Vfix(G)∪Vfree(G)∪Vbad(G) with V0(G) gives the desired equality.
The graph in Figure 2 shows that a fixed vertex need not belong to V+(G). Indeed, {v} is the unique γve(G)-set, while G−v≅P5 and γve(G−v)=γve(G)=1. Hence v∈Vfix0(G).
Theorem 2.16. Let G be a graph and v∈V(G). Then v∈V0(G) if and only if one of the following holds:
(1) v∈Vbad(G);
(2) there exists a γve(G)-set S containing v such that ρS(v,R)≥∣R∣+1 for every R⊆S∖{v}, with equality for at least one such $R.
Proof. Suppose that v∈V0(G). If v∈Vbad(G), then (1) holds. Otherwise, there exists a γve(G)-set S containing v. By Lemma 2.9, we have
R⊆S∖{v}min(ρS(v,R)−∣R∣)=γve(G−v)−γve(G)+1=1.
Hence, ρS(v,R)≥∣R∣+1 for every R⊆S∖{v}, with equality for at least one such $R. Conversely, by Observation 2.15, we have Vbad(G)⊆V0(G). Now suppose that (2) holds. Then
R⊆S∖{v}min(ρS(v,R)−∣R∣)=1.
By Lemma 2.9, γve(G−v)=γve(G). Thus v∈V0(G).
Proposition 2.17. Let G be a graph and v∈V(G).
(1) If v∈V0(G), then ⋃k≥2Vfixk(G)⊆Vfix(G−v).
(2) If v∈Vfree0(G)∪Vbad(G), then Vfix(G)⊆Vgood(G−v).
(3) If v∈Vbad(G), then V−(G)⊆V−(G−v) and, for every u∈NG(v), u∈/V−(G−v).
Proof. (1) Let u∈Vfixk(G) for some k≥2, and S be any γve(G−v)-set. Since v∈V0(G), ∣S∣=γve(G−v)=γve(G). Suppose that u∈/S. Then S∪{v} is a ve-dominating set of G−u. Hence,
γve(G−u)≤∣S∪{v}∣≤γve(G)+1.
On the other hand, since u∈Vfixk(G),
γve(G−u)=γve(G)+k≥γve(G)+2,
a contradiction. Thus u∈S. Since S is arbitrary, u∈Vfix(G−v).
(2) Let v∈Vfree0(G)∪Vbad(G). Then there exists a γve(G)-set S such that v∈/S. By Observation 2.7, S is a ve-dominating set of G−v. Moreover, ∣S∣=γve(G)=γve(G−v), and hence S is a γve(G−v)-set. Since every vertex in Vfix(G) belongs to S, it follows that Vfix(G)⊆Vgood(G−v).
(3) Let v′∈V−(G) and S be a γve(G−v′)-set. Since v∈Vbad(G), by Proposition 2.6(2), we have v∈Vbad(G−v′), so v∈/S. Thus, S is a ve-dominating set of G−{v′,v}. Therefore,
γve(G−{v′,v})≤∣S∣=γve(G)−1=γve(G−v)−1.
Thus v′∈V−(G−v). Hence, V−(G)⊆V−(G−v).
Now suppose that u∈NG(v)∩V−(G−v), and let S′ be a γve(G−{u,v})-set. Since uv∈E(G), the vertex vve-dominates every edge incident with u or v, so S′∪{v}ve-dominates G. Moreover, since v∈Vbad(G)⊆V0(G),
∣S′∪{v}∣=γve(G−{u,v})+1=γve(G−v)=γve(G).
Thus S′∪{v} is a γve(G)-set, contradicting v∈Vbad(G). Hence, u∈/V−(G−v) for every u∈NG(v).
The following theorem extends the private-edge bound in [11 Proposition 2] to fixed vertices without assuming that the minimum ve-dominating set is unique. It also yields the counting bound in Corollary 2.19.
Theorem 2.18. Let G be a graph. For each v∈Vfix(G), let Sv be a γve(G)-set and
Xv={x∈NG(v):x is an endvertex of some e∈peG[v,Sv]∩E(G−v)}.
Then Xv⊆V0(G)∖Vfix0(G) and ∣Xv∣≥max{2,γve(G−v)−γve(G)+1}. Moreover, the sets Xv are pairwise disjoint.
Proof. We first show that ∣Xv∣≥max{2,γve(G−v)−γve(G)+1}. Since v∈Vfix(G), v∈Sv. If Xv=∅, then every private edge of v with respect to Sv is incident with v. Hence, Sv∖{v} is a ve-dominating set of G−v. Thus v∈V−(G), and by Proposition 2.6(1), v∈Vfree(G), which contradicts v∈Vfix(G). If ∣Xv∣=1, write Xv={x}. Then every edge in peG[v,Sv]∩E(G−v) is incident with x. Moreover, since x∈NG(v), the vertex x also ve-dominates every private edge of $v that is incident with v. Thus, xve-dominates every edge in peG[v,Sv]. Every edge outside peG[v,Sv] is ve-dominated by some vertex of Sv∖{v}. Therefore, (Sv∖{v})∪{x} is a ve-dominating set of G. Since x=v is an endvertex of a private edge of v with respect to Sv, we have x∈/Sv. Thus (Sv∖{v})∪{x} is a γve(G)-set not containing v, contradicting v∈Vfix(G). Therefore, ∣Xv∣≥2.
Moreover, Xvve-dominates every private edge of v that remains in G−v. Thus, (Sv∖{v})∪Xv is a ve-dominating set of G−v, and γve(G−v)≤γve(G)−1+∣Xv∣. It follows that ∣Xv∣≥γve(G−v)−γve(G)+1.
We next prove that Xv⊆V0(G)∖Vfix0(G). Let x∈Xv. If x∈V−(G), then v∈NG(x), and Proposition 2.6(2) and (3) gives v∈Vbad(G−x)∩Vfix(G−x), a contradiction. Hence x∈/V−(G). Suppose that x∈Vfix(G). Then x∈Sv. By the definition of Xv, there exists an edge e∈peG[v,Sv]∩E(G−v) incident with x. Thus, xve-dominates e, contradicting the fact that e is a private edge of v with respect to Sv. Hence x∈/Vfix(G), and therefore x∈/V+(G). Thus Xv⊆V0(G)∖Vfix0(G).
Finally, let u,v∈Vfix(G) be distinct and suppose that x∈Xu∩Xv. Since x∈Xv, there exists an edge e∈peG[v,Sv]∩E(G−v) incident with x. Since u∈Vfix(G), we have u∈Sv∖{v} for any choice of Sv. Moreover, x∈Xu⊆NG(u), so uve-dominates e, contradicting e∈peG[v,Sv]. Hence Xu∩Xv=∅, and the sets Xv are pairwise disjoint. □
Corollary 2.19 yields the following characterization of CVRve.
Corollary 2.20. Let G be a graph. Then γve(G)=γve(G−v) for every v∈V(G) if and only if V(G)=V−(G).
Proof. If V(G)=V−(G), then γve(G)=γve(G−v) for every v∈V(G). Suppose that V0(G)=∅. Then by Corollary 2.19, we have 0=∣V0(G)∣≥2∣V+(G)∣. So V+(G)=∅. Since V(G)=V−(G)∪V+(G)∪V0(G), V(G)=V−(G).
It follows from Corollary 2.5 and Corollary 2.20 that G∈CVRve if and only if for all v∈V(G), there exists a γve(G)-set S such that v∈S and peG[v,S]⊆{uv:u∈NG(v)}, where peG[v,S]=∅.
Corollary 2.20 also implies that V0(G)=∅ only if V+(G)=∅. The converse does not hold. For example, if G=K1,n with n≥2, then V+(G)=∅, whereas V0(G)=∅. We next show that V0(T)=∅ for every tree T of order at least three.
Theorem 2.21.For any tree T on n≥3 vertices, V0(T)=∅.
Proof. Let v be the neighbor of an endvertex of a longest path of T. Then d(v)≥2, and v is adjacent to at least one leaf and at most one non-leaf vertex. If v has no non-leaf neighbor, then T is a star. In this case, removing any leaf does not change the ve-domination number, and hence V0(T)=∅. Thus, we may assume that N(v)={u1,…,uk,w}, where k≥1, the vertices u1,…,uk are leaves, and w is a non-leaf vertex.
Suppose that k≥2. Fix i∈{1,…,k} and let S be a γve(T−ui)-set. Since there exists j=i, the edge vuj must be ve-dominated by some vertex of S, and hence S∩N[v]=∅. Therefore, S also ve-dominates the edge vui, so S is a ve-dominating set of T. Thus, γve(T)≤γve(T−ui). Since d(ui)=1, Theorem 2.1 gives γve(T−ui)≤γve(T). Hence γve(T−ui)=γve(T), and therefore ui∈V0(T).
Now suppose that k=1. Then v is adjacent to exactly one leaf u1 and d(v)=2. Since d(u1)=1, γve(T−u1)≤γve(T). In addition, by Theorem 2.1, γve(T)≤γve(T−u1)+1. Hence, we have γve(T−u1)=γve(T) or γve(T−u1)=γve(T)−1. In the first case, u1∈V0(T). In the second case, u1∈V−(T). By Theorem 2.13, we have v∈/V+(T). If v∈V0(T), the conclusion follows. It remains to consider v∈V−(T).
Let H=T−{w,v,u1}. Since T−w is the disjoint union of H and the edge vu1, γve(T−w)=γve(H)+1. A γve(H)-set together with wve-dominates T, so
γve(T)≤γve(H)+1=γve(T−w).
Thus w∈/V−(T). Moreover, since vw∈E(T) and v∈V−(T), Theorem 2.13 gives w∈/V+(T). Hence w∈V0(T).
:::
The next result relates the vertices in Vfix0(G) to cycles in G.
Theorem 2.22.Let G be a graph and v∈V(G). If v∈Vfix0(G), then there exists a cycle C in G such that v∈V(C).
Proof. Let v∈Vfix0(G). Since the ve-domination number is additive over components, we may assume that G is connected. Suppose that there is no cycle containing v in $G. Since v∈Vfix0(G), v is not isolated. Let N(v)={u1,…,ur}. Then distinct vertices in N(v) belong to distinct components of G−v; otherwise, there exists a cycle containing v. Let these components be H1,…,Hr, where ui∈V(Hi). Then each ui is the only vertex of Hi adjacent to v. For each i, let
ai=min{∣A∣:A⊆V(Hi) and A∪{v}ve-dominates G[V(Hi)∪{v}]}.
Set bi=γve(Hi), and choose Bi∈S(Hi). Since Bi∪{v}ve-dominates G[V(Hi)∪{v}], we have ai≤∣Bi∣=bi. Moreover, since ui is the only vertex of Hi adjacent to v, adding ui suffices to ve-dominate all edges of Hi that may be ve-dominated by v. Thus bi≤ai+1. Hence
bi−ai∈{0,1}.(4)
Let S be a γve(G)-set. Since v is fixed, v∈S. For each i, no vertex of another component of G−v can ve-dominate an edge of Hi, so ∣S∩V(Hi)∣≥ai. Conversely, if Ai attains ai for each i, then {v}∪⋃i=1rAive-dominates G. Hence
γve(G)=1+i=1∑rai.(5)
On the other hand,
γve(G−v)=i=1∑rbi.(6)
Since v∈Vfix0(G), γve(G−v)=γve(G).
By (4)–(6), we have ∑i=1r(bi−ai)=1. Hence, there is a unique index j such that bj=aj+1, while bi=ai for every i=j. Choose Aj attaining aj, and for each i=j, choose Bi∈S(Hi). Then Aj∪{uj} is a ve-dominating set of Hj. We have uj∈/Aj; otherwise, Aj would ve-dominate Hj, contradicting bj=aj+1. Since ∣Aj∪{uj}∣=aj+1=bj, the set Aj∪{uj} is a γve(Hj)-set. Let D=(⋃i=jBi)∪Aj∪{uj}. Then Dve-dominates every edge of G−v. Moreover, since uj∈N(v), the vertex ujve-dominates every edge incident with v. Therefore, D is also a ve-dominating set of G. Furthermore,
∣D∣=i=1∑rbi=γve(G−v)=γve(G),
so D is a γve(G)-set not containing v, contradicting v∈Vfix(G).
Corollary 2.23
Corollary 2.23. For every forest F, Vfix(F)=V+(F).
Proof. By Proposition 2.6(1) and Proposition 2.8, Vfix(F)=Vfix0(F)∪V+(F). Since F contains no cycle, Theorem 2.22 gives Vfix0(F)=∅, and the result follows.
This extends the implication (i)⇒(iii) of [11 Theorem 7] to fixed vertices in arbitrary forests, without assuming that the minimum ve-dominating set is unique.
Conclusion
In this paper, we studied the effect of vertex removal on the vertex-edge domination number. We established sharp bounds on γve(G−v) and characterized the three vertex classes V−(G), V0(G), and V+(G). We also introduced an exchange parameter, derived a weighted counting bound, and proved that every fixed vertex in V0(G) lies on a cycle.
Our results imply that a nonempty forest F belongs to CVRve if and only if each component is isomorphic to K2. Indeed, every isolated vertex belongs to V0(F). By Theorem 2.21 and additivity, every component of order at least three also contains a vertex of V0(F). Conversely, if all components are copies of K2, deleting any vertex decreases γve(F) by one.
For paths and cycles, the standard formulas (see Peters [10] and Lewis [7 Proposition 23]) are
γve(Pm)=⌈4m−1⌉(m≥1),γve(Cn)=⌈4n⌉(n≥3).
Since Cn−v≅Pn−1 for every v∈V(Cn), we have Cn∈CVRve if and only if n≡1,2(mod4).
It would be interesting to obtain further structural characterizations of graphs in CVRve, to characterize graphs satisfying V0(G)=V(G), and to determine whether the coefficients in the weighted bound of Corollary 2.19 can be improved.
References
[1]K. Bartolo, P. Borg, M. Dettlaff, M. Lemańska, P. Żyliński, Isolation critical graphs under multiple edge subdivision, arXiv:2602.22980v2 (2026).arxiv.org/abs/2602.22980
[2]R. Boutrig, M. Chellali, T. W. Haynes, S. T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016) 355–366.DOI
[3]Y. Caro, A. Hansberg, Partial domination—the isolation number of a graph, Filomat 31 (2017) 3925–3944.DOI
[4]S. K. Jena, G. K. Das, Vertex-edge domination in unit disk graphs, Discrete Appl. Math. 319 (2022) 351–361.
[5]W. F. Klostermeyer, M. E. Messinger, A. Yeo, Dominating vertex covers: the vertex-edge domination problem, Discuss. Math. Graph Theory 41 (2021) 123–132.
[6]B. Krishnakumari, Y. B. Venkatakrishnan, M. Krzywkowski, Bounds on the vertex-edge domination number of a tree, C. R. Math. Acad. Sci. Paris 352 (2014) 363–366.DOI
[7]J. R. Lewis, Vertex-Edge and Edge-Vertex Parameters in Graphs, Ph.D. dissertation, Clemson University, 2007.
[8]J. R. Lewis, S. T. Hedetniemi, T. W. Haynes, G. H. Fricke, Vertex-edge domination, Util. Math. 81 (2010) 193–213.
[9]S. Paul, K. Ranjan, Results on vertex-edge and independent vertex-edge domination, J. Comb. Optim. 44 (2022) 303–330.DOI
[10]K. W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, Ph.D. dissertation, Clemson University, 1986.
[11]B. Senthilkumar, M. Chellali, H. Naresh Kumar, Y. B. Venkatakrishnan, Graphs with unique minimum vertex-edge dominating sets, RAIRO Oper. Res. 57 (2023) 1785–1795.
[12]D. K. Thakkar, N. P. Jamvecha, About ve-domination in graphs, Ann. Pure Appl. Math. 14 (2017) 245–250.DOI
[13]R. Ziemann, P. Żyliński, Vertex-edge domination in cubic graphs, Discrete Math. 343 (2020) 112075.DOI