betaFeedback

WorksMathematics

Vertex Removal and Vertex-Edge Domination

Abstract

A vertex vv of a graph GG veve-dominates every edge incident with a vertex in its closed neighborhood NG[v]N_{G}[v]. A set of vertices is a vertex-edge dominating set (veve-dominating set) if every edge of GG is veve-dominated by some vertex in the set. The minimum cardinality of such a set is the vertex-edge domination number γve(G)γ_{ve}(G), also known as the isolation number. In this paper, we study the effect of vertex removal on γve(G)γ_{ve}(G), establish sharp bounds on γve(G−v)γ_{ve}(G-v) and characterize the vertices whose removal decreases, preserves, or increases γve(G)γ_{ve}(G). Let V0(G)V^0(G) and V+(G)V^+(G) denote the sets of vertices whose removal preserves and increases γve(G)γ_{ve}(G), respectively, and let Vfix0(G)V_{\mathrm{fix}}^0(G) consist of the vertices in V0(G)V^0(G) belonging to every minimum veve-dominating set. We prove that ∣V0(G)∣≥3∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1). |V^0(G)|\geq3|V_{\mathrm{fix}}^0(G)|+\sum_{v\in V^+(G)} \bigl(γ_{ve}(G-v)-γ_{ve}(G)+1\bigr). In particular, ∣V0(G)∣≥2∣V+(G)∣|V^0(G)|\geq 2|V^+(G)|. We also prove that every vertex in Vfix0(G)V_{\mathrm{fix}}^0(G) lies on a cycle and that V0(T)≠∅V^0(T)\neq\emptyset for every tree TT of order at least three.

Introduction

All graphs considered in this paper are finite, simple, and undirected. For a graph GG, let V(G)V(G) and E(G)E(G) denote its vertex set and edge set, respectively. The open neighborhood of a vertex vv is NG(v)={u∈V(G):uv∈E(G)}N_G(v) = \{u \in V(G) : uv \in E(G)\}, and its closed neighborhood is NG[v]=NG(v)∪{v}N_G[v] = N_G(v) \cup\{v\}. The degree of vv is d(v)=∣NG(v)∣d(v) = |N_G(v)|. A vertex vv is called an isolated vertex if d(v)=0d(v) = 0. If d(v)=1d(v) = 1, then vv is called a leaf. For S⊆V(G)S \subseteq V(G), let NG(S)=⋃v∈SNG(v)N_G(S) = \bigcup_{v\in S} N_G(v) and NG[S]=NG(S)∪SN_G[S] = N_G(S) \cup S. Note that NG(S)N_G(S) may contain vertices of SS. We omit the subscript GG when the graph is clear from the context.

For any S⊆V(G)S \subseteq V(G), let G[S]G[S] denote the subgraph induced by SS, and write G−S=G[V(G)∖S]G - S = G[V(G) \setminus S]. We abbreviate G−{v}G - \{v\} to G−vG-v. A set SS is independent if G[S]G[S] is edgeless. For E′⊆E(G)E' \subseteq E(G), let G[E′]G[E'] denote the edge subgraph with edge set E′E' and vertex set consisting of the endvertices of edges in E′E'. The path, cycle, and star of order nn are denoted by PnP_n, CnC_n, and K1,n−1K_{1,n-1}, respectively; 2K22K_2 denotes the disjoint union of two edges. A forest is a graph containing no cycle, and a tree is a connected forest. The distance d(u,v)d(u,v) between two vertices uu and vv in a graph GG is the length of a shortest path in GG which connects uu and vv, and d(u,v)=∞d(u,v) = \infty when uu and vv belong to distinct components.

For any vertex vv in a graph GG, we say that vv ve-dominates every edge in GG which is incident with some vertex in N[v]N[v]. A subset S⊆V(G)S \subseteq V(G) is a vertex-edge dominating set of GG, abbreviated ve-dominating set, if every edge ee in GG is ve-dominated by some vertex vv in SS. The vertex-edge domination number, abbreviated ve-domination number, of GG is the minimum cardinality of a ve-dominating set of GG, denoted by γve(G)\gamma_{ve}(G). We call a ve-dominating set of cardinality γve(G)\gamma_{ve}(G) a γve(G)\gamma_{ve}(G)-set. Equivalently, SS is a ve-dominating set if and only if G−N[S]G - N[S] is edgeless. Thus, γve(G)\gamma_{ve}(G) equals the isolation number ι(G)\iota(G) studied by Caro and Hansberg [3]. When GG is edgeless or GG has no vertices, γve(G)=0\gamma_{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)\gamma_{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: vv dominates xyxy when {x,y}⊆N[v]\{x,y\} \subseteq N[v]. Our definition requires only {x,y}∩N[v]≠∅\{x,y\} \cap N[v] \ne\varnothing. In this paper, we study the effect of vertex removal on γve(G)\gamma_{ve}(G) by examining the structure of γve(G)\gamma_{ve}(G)-sets.

Removing a vertex may decrease, preserve, or increase the veve-domination number. Accordingly, we partition V(G)V(G) into the following three classes:

V−(G)={v∈V(G):γve(G−v)<γve(G)},V^{-}(G)=\{v\in V(G):\gamma_{ve}(G-v)<\gamma_{ve}(G)\},
V0(G)={v∈V(G):γve(G−v)=γve(G)},V^{0}(G)=\{v\in V(G):\gamma_{ve}(G-v)=\gamma_{ve}(G)\},
V+(G)={v∈V(G):γve(G−v)>γve(G)}.V^{+}(G)=\{v\in V(G):\gamma_{ve}(G-v)>\gamma_{ve}(G)\}.

Let CVRve\mathcal{C}\mathcal{V}\mathcal{R}_{ve} denote the class of vertex-edge domination vertex-critical graphs, or γve\gamma_{ve}-vertex-critical graphs for short, consisting of all graphs GG satisfying γve(G)≠γve(G−v)\gamma_{ve}(G)\ne\gamma_{ve}(G-v) for every v∈V(G)v\in V(G). Thus G∈CVRveG\in\mathcal{C}\mathcal{V}\mathcal{R}_{ve} if and only if V0(G)=∅V^{0}(G)=\varnothing.

The vertices of GG can also be classified in terms of γve(G)\gamma_{ve}(G)-sets as follows. Let S(G)\mathcal{S}(G) denote the family of all γve(G)\gamma_{ve}(G)-sets, and let S(v,G)={S∈S(G):v∈S}\mathcal{S}(v,G)=\{S\in\mathcal{S}(G):v\in S\}. A vertex vv is γve(G)\gamma_{ve}(G)-good if v∈Sv\in S for some γve(G)\gamma_{ve}(G)-set SS, and γve(G)\gamma_{ve}(G)-bad if v∉Sv\notin S for every γve(G)\gamma_{ve}(G)-set SS. It is γve(G)\gamma_{ve}(G)-fixed if v∈Sv\in S for every γve(G)\gamma_{ve}(G)-set SS, and γve(G)\gamma_{ve}(G)-free if vv is contained in some γve(G)\gamma_{ve}(G)-set but not in all γve(G)\gamma_{ve}(G)-sets. The corresponding sets are denoted by Vgood(G),Vbad(G),Vfix(G),Vfree(G)V_{\mathrm{good}}(G),V_{\mathrm{bad}}(G),V_{\mathrm{fix}}(G),V_{\mathrm{free}}(G), respectively. In particular, the fixed, free, and bad vertices form a partition of V(G)V(G). We further define

Vfree0(G)=Vfree(G)∩V0(G),V_{\mathrm{free}}^{0}(G)=V_{\mathrm{free}}(G)\cap V^{0}(G),
Vfree−(G)=Vfree(G)∩V−(G),V_{\mathrm{free}}^{-}(G)=V_{\mathrm{free}}(G)\cap V^{-}(G),
Vfixk(G)={v∈Vfix(G):γve(G−v)=γve(G)+k}(k≥0),V_{\mathrm{fix}}^{k}(G)=\{v\in V_{\mathrm{fix}}(G):\gamma_{ve}(G-v)=\gamma_{ve}(G)+k\}\quad(k\ge0),

where kk is an integer. In particular, Vfix0(G)=Vfix(G)∩V0(G)V_{\mathrm{fix}}^{0}(G)=V_{\mathrm{fix}}(G)\cap V^{0}(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):

∣V0(G)∣≥3∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1).|V^{0}(G)|\ge3|V_{\mathrm{fix}}^{0}(G)|+\sum_{v\in V^{+}(G)}\left(\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\right).

We also prove that every vertex in Vfix0(G)V_{\mathrm{fix}}^{0}(G) lies on a cycle (Theorem 2.22) and that V0(T)≠∅V^{0}(T)\ne\varnothing for every tree TT 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 veve-domination number. We begin with sharp bounds on the veve-domination number after the removal of a vertex.

Theorem 2.1. Let GG be a graph and v∈V(G)v \in V(G) be a non-isolated vertex. Then

γve(G)−1≤γve(G−v)≤γve(G)+d(v)−1.(1)\gamma_{ve}(G) - 1 \le\gamma_{ve}(G-v) \le\gamma_{ve}(G) + d(v) - 1. \tag*{(1)}

The lower bound also holds for isolated vertices. Moreover, the bounds are sharp.

Proof. Let SS be a γve(G−v)\gamma_{ve}(G-v)-set. Then S∪{v}S \cup\{v\} is a veve-dominating set of GG. Hence γve(G)≤γve(G−v)+1\gamma_{ve}(G) \le\gamma_{ve}(G-v) + 1, that is, γve(G−v)≥γve(G)−1\gamma_{ve}(G-v) \ge\gamma_{ve}(G) - 1.

Now we prove that γve(G−v)≤γve(G)+d(v)−1\gamma_{ve}(G-v) \le\gamma_{ve}(G) + d(v) - 1. Let S′S' be a γve(G)\gamma_{ve}(G)-set. If v∈S′v \in S', then (S′∖{v})∪N(v)(S' \setminus\{v\}) \cup N(v) is a veve-dominating set of G−vG-v, since every edge of G−vG-v veve-dominated by vv is incident with a vertex of N(v)N(v). Therefore, we have γve(G−v)≤γve(G)+d(v)−1\gamma_{ve}(G-v) \le\gamma_{ve}(G) + d(v) - 1.

If v∉S′v \notin S', then S′S' is also a veve-dominating set of G−vG-v, so γve(G−v)≤γve(G)\gamma_{ve}(G-v) \le\gamma_{ve}(G). Hence, we have γve(G−v)≤γve(G)+d(v)−1\gamma_{ve}(G-v) \le\gamma_{ve}(G) + d(v) - 1, where the last inequality follows from d(v)≥1d(v) \ge1.

For sharpness of the lower bound, let G=K1,kG = K_{1,k}, where k≥1k \ge1, and let vv be its center. Then γve(G)=1\gamma_{ve}(G) = 1 and γve(G−v)=0\gamma_{ve}(G-v) = 0. For sharpness of the upper bound, let GG be obtained from K1,rK_{1,r} (r≥1r \ge1) by subdividing each edge once, and let vv be the original center. Then {v}\{v\} veve-dominates GG, while G−v≅rK2G-v \cong rK_2. Hence γve(G−v)=r=γve(G)+d(v)−1\gamma_{ve}(G-v) = r = \gamma_{ve}(G) + d(v) - 1.

Theorem 2.1 shows that removing a non-isolated vertex vv decreases the veve-domination number by at most one, while it may increase the veve-domination number by as much as d(v)−1d(v) - 1. Consequently, we have the following.

Corollary 2.2. Let GG be a graph and v∈V(G)v \in V(G). If v∈V−(G)v \in V^{-}(G), then γve(G−v)=γve(G)−1\gamma_{ve}(G-v) = \gamma_{ve}(G) - 1. If v∈V+(G)v \in V^{+}(G), then γve(G−v)=γve(G)+r\gamma_{ve}(G-v) = \gamma_{ve}(G) + r for some integer rr with 1≤r≤d(v)−11 \le r \le d(v) - 1.

On vertices in V−(G)V^{-}(G)

In this subsection, we characterize the vertices in V−(G)V^{-}(G) in terms of private edges of minimum veve-dominating sets.

Recall that, for S⊆V(G)S \subseteq V(G) and v∈Sv \in S, an edge e∈E(G)e \in E(G) is a private edge of vv with respect to SS if vv ve-dominates ee and no vertex of S∖{v}S \setminus\{v\} does. The set of all such edges is denoted by peG[v,S]pe_G[v,S].

Observation 2.3. Let GG be a graph and v∈V−(G)v \in V^{-}(G). Then for every S∈S(G−v)S \in\mathcal{S}(G-v) and every u∈NG[v]u \in N_G[v], S∪{u}∈S(G)S \cup\{u\} \in\mathcal{S}(G).

Proof. Let S∈S(G−v)S \in\mathcal{S}(G-v) and u∈NG[v]u \in N_G[v]. By Corollary 2.2, ∣S∣=γve(G)−1|S| = \gamma_{ve}(G)-1. The set SS ve-dominates every edge of G−vG-v, and uu ve-dominates every edge incident with vv. Thus S∪{u}S \cup\{u\} is a ve-dominating set of GG, and

γve(G)≤∣S∪{u}∣≤∣S∣+1=γve(G).\gamma_{ve}(G) \le|S \cup\{u\}| \le|S|+1 = \gamma_{ve}(G).

Hence S∪{u}∈S(G)S \cup\{u\} \in\mathcal{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 GG be a graph and v∈V(G)v \in V(G). Then v∈V−(G)v \in V^{-}(G) if and only if there exists a γve(G)\gamma_{ve}(G)-set SS with v∈Sv \in S such that ∅≠peG[v,S]⊆{uv:u∈NG(v)}\varnothing\ne pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}.

Proof. Suppose first that v∈V−(G)v \in V^{-}(G), and let S′S' be a γve(G−v)\gamma_{ve}(G-v)-set. By Observation 2.3, S=S′∪{v}S = S' \cup\{v\} is a γve(G)\gamma_{ve}(G)-set. If peG[v,S]=∅pe_G[v,S] = \varnothing, then S′S' is a ve-dominating set of GG, contradicting the assumption that v∈V−(G)v \in V^{-}(G). Thus, peG[v,S]≠∅pe_G[v,S] \ne\varnothing. Now we prove peG[v,S]⊆{uv:u∈NG(v)}pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}. If there exists some edge e∈peG[v,S]e \in pe_G[v,S] that is not incident with vv, then e∈E(G−v)e \in E(G-v) and it is not ve-dominated by any vertex in S′S'. This contradicts the assumption that S′S' is a γve\gamma_{ve}-set of G−vG-v. Hence, peG[v,S]⊆{uv:u∈NG(v)}pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}.

Conversely, suppose that there exists a γve(G)\gamma_{ve}(G)-set SS with v∈Sv \in S such that peG[v,S]≠∅pe_G[v,S] \ne\varnothing and peG[v,S]⊆{uv:u∈NG(v)}pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}. Then peG[v,S]∩E(G−v)=∅pe_G[v,S] \cap E(G-v) = \varnothing, implying that S∖{v}S \setminus\{v\} is a ve-dominating set of G−vG-v. Thus, γve(G−v)≤∣S∣−1=γve(G)−1\gamma_{ve}(G-v) \le|S|-1 = \gamma_{ve}(G)-1. Hence v∈V−(G)v \in V^{-}(G).

The following result is a consequence of Theorem 2.4.

Corollary 2.5. Let GG be a graph. Then V(G)=V−(G)V(G) = V^{-}(G) if and only if for every v∈V(G)v \in V(G), there exists a γve(G)\gamma_{ve}(G)-set SS such that v∈Sv \in S and ∅≠peG[v,S]⊆{uv:u∈NG(v)}\varnothing\ne pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}.

Next, we present several properties of v∈V−(G)v \in V^{-}(G).

Proposition 2.6. Let GG be a graph. Then the following statements hold:

  1. V−(G)=Vfree−(G)V^{-}(G) = V^{-}_{\mathrm{free}}(G);

  2. For every v∈V−(G)v \in V^{-}(G), Vbad(G)∪NG(v)⊆Vbad(G−v)V_{\mathrm{bad}}(G) \cup N_G(v) \subseteq V_{\mathrm{bad}}(G-v);

  3. For every v∈V−(G)v \in V^{-}(G), Vfix(G)⊆Vfix(G−v)V_{\mathrm{fix}}(G) \subseteq V_{\mathrm{fix}}(G-v).

Proof. (1) Since Vfree−(G)=Vfree(G)∩V−(G)V_{\mathrm{free}}^{-}(G)=V_{\mathrm{free}}(G)\cap V^{-}(G), Vfree−(G)⊆V−(G)V_{\mathrm{free}}^{-}(G)\subseteq V^{-}(G). Conversely, let v∈V−(G)v\in V^{-}(G) and S′S' be a γve(G−v)\gamma_{ve}(G-v)-set. Since isolated vertices belong to V0(G)V^{0}(G), we have NG(v)≠∅N_G(v)\ne\varnothing. Then by Observation 2.3, both S′∪{v}S'\cup\{v\} and S′∪{u}S'\cup\{u\} are γve(G)\gamma_{ve}(G)-sets, where u∈NG(v)u\in N_G(v). Thus, vv is γve(G)\gamma_{ve}(G)-free. Hence V−(G)⊆Vfree−(G)V^{-}(G)\subseteq V_{\mathrm{free}}^{-}(G).

(2) For any u∈NG(v)u\in N_G(v), suppose that u∉Vbad(G−v)u\notin V_{\mathrm{bad}}(G-v). Then there exists a γve(G−v)\gamma_{ve}(G-v)-set SS containing uu. Since uu veve-dominates every edge incident with vv, SS is also a veve-dominating set of GG. Hence γve(G)≤∣S∣=γve(G)−1\gamma_{ve}(G)\le|S|=\gamma_{ve}(G)-1, a contradiction. Thus NG(v)⊆Vbad(G−v)N_G(v)\subseteq V_{\mathrm{bad}}(G-v).

Let w∈Vbad(G)w\in V_{\mathrm{bad}}(G). If there is a set S∈S(w,G−v)S\in\mathcal{S}(w,G-v), then S∪{v}∈S(w,G)S\cup\{v\}\in\mathcal{S}(w,G). This contradicts w∈Vbad(G)w\in V_{\mathrm{bad}}(G). Thus, we have w∈Vbad(G−v)w\in V_{\mathrm{bad}}(G-v). Hence Vbad(G)∪NG(v)⊆Vbad(G−v)V_{\mathrm{bad}}(G)\cup N_G(v)\subseteq V_{\mathrm{bad}}(G-v).

(3) By (1), v∉Vfix(G)v\notin V_{\mathrm{fix}}(G). Let v′∈Vfix(G)v'\in V_{\mathrm{fix}}(G) and S′S' be any γve(G−v)\gamma_{ve}(G-v)-set. By Observation 2.3, S′∪{v}S'\cup\{v\} is a γve(G)\gamma_{ve}(G)-set. Since v′≠vv'\ne v and v′∈Vfix(G)v'\in V_{\mathrm{fix}}(G), we have v′∈S′v'\in S'. Thus v′∈Vfix(G−v)v'\in V_{\mathrm{fix}}(G-v), and hence Vfix(G)⊆Vfix(G−v)V_{\mathrm{fix}}(G)\subseteq V_{\mathrm{fix}}(G-v).

On vertices in V+(G)V^{+}(G)

In this subsection, we characterize the vertices v∈V+(G)v\in V^{+}(G). The following observation follows directly from the definition.

Observation 2.7. Let GG be a graph and S∈S(G)S\in\mathcal{S}(G). Then for every vertex v∈V(G)∖Sv\in V(G)\setminus S, SS is a veve-dominating set of G−vG-v.

Proposition 2.8. Let GG be a graph and v∈V(G)v\in V(G). If v∈V+(G)v\in V^{+}(G), then v∈Vfix(G)v\in V_{\mathrm{fix}}(G).

Proof. Let v∈V+(G)v\in V^{+}(G). Suppose that v∉Vfix(G)v\notin V_{\mathrm{fix}}(G). Then there exists a γve(G)\gamma_{ve}(G)-set SS with v∉Sv\notin S. By Observation 2.7, SS is also a veve-dominating set of G−vG-v. Thus, γve(G−v)≤∣S∣=γve(G)\gamma_{ve}(G-v)\le|S|=\gamma_{ve}(G). This contradicts v∈V+(G)v\in V^{+}(G).

By Proposition 2.8, no free vertex belongs to V+(G)V^{+}(G). Thus Vfree(G)=Vfree−(G)∪Vfree0(G)V_{\mathrm{free}}(G)=V_{\mathrm{free}}^{-}(G)\cup V_{\mathrm{free}}^{0}(G).

To characterize the vertices in V+(G)V^{+}(G), we introduce the following exchange parameter. Let SS be a γve(G)\gamma_{ve}(G)-set containing the vertex vv. For R⊆S∖{v}R\subseteq S\setminus\{v\}, define

ρS(v,R)=min⁡{∣X∣:X⊆V(G)∖S and (S∖(R∪{v}))∪X ve-dominates G−v}.\rho_S(v,R)=\min\{|X|:X\subseteq V(G)\setminus S\text{ and }(S\setminus(R\cup\{v\}))\cup X\text{ }ve\text{-dominates }G-v\}.

We call ρS(v,R)\rho_S(v,R) the exchange number of vv with respect to SS and RR. Every vertex of SS has a neighbor outside SS; otherwise, it would have no private edge, contradicting the minimality of SS. Thus V(G)∖SV(G)\setminus S dominates G−vG-v, so X=V(G)∖SX=V(G)\setminus S is feasible for every R⊆S∖{v}R\subseteq S\setminus\{v\}. Consequently,

0≤ρS(v,R)≤∣V(G)∖S∣.0\le\rho_S(v,R)\le|V(G)\setminus S|.

Lemma 2.9. Let GG be a graph, v∈V(G)v \in V(G), and SS be a γve(G)\gamma_{ve}(G)-set containing vv. Then

γve(G−v)=γve(G)−1+min⁡R⊆S∖{v}(ρS(v,R)−∣R∣).\gamma_{ve}(G-v)=\gamma_{ve}(G)-1+\min_{R\subseteq S\setminus\{v\}}\left(\rho_S(v,R)-|R|\right).

Proof. For any R⊆S∖{v}R\subseteq S\setminus\{v\}, let X⊆V(G)∖SX\subseteq V(G)\setminus S be a set of cardinality ρS(v,R)\rho_S(v,R) such that D=(S∖(R∪{v}))∪XD=(S\setminus(R\cup\{v\}))\cup X is a veve-dominating set of G−vG-v. Since X∩S=∅X\cap S=\varnothing, we have

∣D∣=γve(G)−1−∣R∣+ρS(v,R).|D|=\gamma_{ve}(G)-1-|R|+\rho_S(v,R).

Therefore,

γve(G−v)≤γve(G)−1+min⁡R⊆S∖{v}(ρS(v,R)−∣R∣).(2)\gamma_{ve}(G-v)\leq\gamma_{ve}(G)-1+\min_{R\subseteq S\setminus\{v\}}\left(\rho_S(v,R)-|R|\right). \tag*{(2)}

Conversely, let DD be a γve(G−v)\gamma_{ve}(G-v)-set, and let

R=(S∖{v})∖DandX=D∖S.R=(S\setminus\{v\})\setminus D \qquad\text{and}\qquad X=D\setminus S.

Then R⊆S∖{v}R\subseteq S\setminus\{v\}, X⊆V(G)∖SX\subseteq V(G)\setminus S, and D=(S∖(R∪{v}))∪XD=(S\setminus(R\cup\{v\}))\cup X. Hence, by the definition of ρS(v,R)\rho_S(v,R), ρS(v,R)≤∣X∣\rho_S(v,R)\leq|X|.

Moreover,

∣D∣=γve(G)−1−∣R∣+∣X∣≥γve(G)−1+ρS(v,R)−∣R∣.|D|=\gamma_{ve}(G)-1-|R|+|X|\geq\gamma_{ve}(G)-1+\rho_S(v,R)-|R|.

It follows that

γve(G−v)≥γve(G)−1+min⁡R′⊆S∖{v}(ρS(v,R′)−∣R′∣).(3)\gamma_{ve}(G-v)\geq\gamma_{ve}(G)-1+\min_{R'\subseteq S\setminus\{v\}}\left(\rho_S(v,R')-|R'|\right). \tag*{(3)}

By (2) and (3), we have

γve(G−v)=γve(G)−1+min⁡R⊆S∖{v}(ρS(v,R)−∣R∣).\gamma_{ve}(G-v)=\gamma_{ve}(G)-1+\min_{R\subseteq S\setminus\{v\}}\left(\rho_S(v,R)-|R|\right).

Theorem 2.10. Let GG be a graph and v∈V(G)v\in V(G). Then v∈V+(G)v\in V^{+}(G) if and only if there exists a γve(G)\gamma_{ve}(G)-set SS containing vv such that ρS(v,R)≥∣R∣+2\rho_S(v,R)\geq|R|+2 for every R⊆S∖{v}R\subseteq S\setminus\{v\}.

Proof. Suppose that v∈V+(G)v\in V^{+}(G), and let SS be a γve(G)\gamma_{ve}(G)-set. By Proposition 2.8, v∈Sv\in S. By Lemma 2.9, we have

min⁡R⊆S∖{v}(ρS(v,R)−∣R∣)=γve(G−v)−γve(G)+1≥2.\min_{R\subseteq S\setminus\{v\}}\left(\rho_S(v,R)-|R|\right)=\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\geq2.

Hence ρS(v,R)≥∣R∣+2\rho_S(v,R)\geq|R|+2 for every R⊆S∖{v}R\subseteq S\setminus\{v\}.

Conversely, suppose that such a set SS exists. By Lemma 2.9,

γve(G−v)=γve(G)−1+min⁡R⊆S∖{v}(ρS(v,R)−∣R∣)≥γve(G)+1.\gamma_{ve}(G-v)=\gamma_{ve}(G)-1+\min_{R\subseteq S\setminus\{v\}}\left(\rho_S(v,R)-|R|\right)\geq\gamma_{ve}(G)+1.

Thus v∈V+(G)v\in V^{+}(G).

To further investigate the structure of vertices in V+(G)V^{+}(G), we first establish the following lemma concerning the vertex-edge domination number.

Lemma 2.11. Let GG be a graph. If γve(G)≥2\gamma_{ve}(G)\geq2, then GG contains either an induced copy of 2K22K_2 or a copy of C5C_5.

Proof. Suppose that γve(G)≥2\gamma_{ve}(G)\geq2 and that GG contains neither an induced copy of 2K22K_2 nor a copy of C5C_5. Let vv be a vertex of maximum degree in GG. We claim that {v}\{v\} is a veve-dominating set of GG.

Suppose not. Then G−N[v]G-N[v] contains an edge xyxy. For every u∈N(v)u\in N(v), the edges vuvu and xyxy do not induce a 2K22K_2. Since vv is adjacent to neither xx nor yy, the vertex uu must be adjacent to at least one of xx and yy.

Let

A=N(v)∩N(x)andB=N(v)∩N(y).A=N(v)\cap N(x)\qquad\text{and}\qquad B=N(v)\cap N(y).

Then

A∪B=N(v).A\cup B=N(v).

If there exist u∈A∖Bu\in A\setminus B and z∈B∖Az\in B\setminus A, then v−u−x−y−z−vv-u-x-y-z-v forms a C5C_5, a contradiction. Hence either A⊆BA\subseteq B or B⊆AB\subseteq A.

Without loss of generality, suppose that A⊆BA\subseteq B. Then B=N(v)B=N(v). Since xy∈E(G)xy\in E(G) and x∉N[v]x\notin N[v], we have

d(y)≥∣N(v)∣+1=d(v)+1,d(y)\geq|N(v)|+1=d(v)+1,

contradicting the choice of vv as a vertex of maximum degree. Therefore, {v}\{v\} is a veve-dominating set of GG, and hence γve(G)=1\gamma_{ve}(G)=1, a contradiction.

The converse of Lemma 2.11 does not hold in general. For example, take an induced 2K22K_2 and add a vertex adjacent to all four of its vertices. Then this new vertex veve-dominates every edge of the resulting graph.

We now apply Lemma 2.11 to the private edges of a vertex in V+(G)V^{+}(G).

Theorem 2.12. Let GG be a graph and v∈V+(G)v\in V^{+}(G). For any γve(G)\gamma_{ve}(G)-set SS, let U=V(G[pe⁡G[v,S]])∖{v}U=V(G[\operatorname{pe}_G[v,S]])\setminus\{v\}. Then the vertex-induced subgraph G[U]G[U] contains either an induced copy of 2K22K_2 or a copy of C5C_5.

Proof. Since v∈V+(G)v \in V^{+}(G), by Proposition 2.8, we have v∈Vfix(G)v \in V_{\mathrm{fix}}(G), and hence v∈Sv \in S. We claim that γve(G[U])≥2\gamma_{\mathrm{ve}}(G[U]) \ge2.

If E(G[U])=∅E(G[U]) = \varnothing, then every private edge of vv with respect to SS is incident with vv. Thus, S∖{v}S \setminus\{v\} is a ve-dominating set of G−vG-v, contradicting v∈V+(G)v \in V^{+}(G). Hence E(G[U])≠∅E(G[U]) \ne\varnothing.

Suppose that γve(G[U])=1\gamma_{\mathrm{ve}}(G[U])=1, and let x∈Ux \in U be a ve-dominating vertex of G[U]G[U]. Every edge in E(G−v)∖peG[v,S]E(G-v) \setminus pe_G[v,S] is ve-dominated by some vertex of S∖{v}S \setminus\{v\}, while every edge in peG[v,S]∩E(G−v)pe_G[v,S] \cap E(G-v) belongs to G[U]G[U] and is ve-dominated by xx. Therefore, (S∖{v})∪{x}(S \setminus\{v\}) \cup\{x\} is a ve-dominating set of G−vG-v. Consequently,

γve(G−v)≤∣(S∖{v})∪{x}∣≤∣S∣=γve(G),\gamma_{\mathrm{ve}}(G-v) \le\lvert(S \setminus\{v\}) \cup\{x\} \rvert\le\lvert S \rvert= \gamma_{\mathrm{ve}}(G),

contradicting v∈V+(G)v \in V^{+}(G). Thus γve(G[U])≥2\gamma_{\mathrm{ve}}(G[U]) \ge2. By Lemma 2.11, G[U]G[U] contains either an induced 2K22K_2 or a C5C_5.

The next theorem shows that no vertex of V+(G)V^{+}(G) is adjacent to a vertex of V−(G)V^{-}(G).

Theorem 2.13. For two vertices u∈V+(G)u \in V^{+}(G) and v∈V−(G)v \in V^{-}(G), d(u,v)≥2d(u,v) \ge2. Moreover, the bound is sharp.

Proof. Clearly, uu and vv are not isolated vertices. Suppose that there exist two vertices u∈V+(G)u \in V^{+}(G) and v∈V−(G)v \in V^{-}(G) such that d(u,v)<2d(u,v) < 2. Then uv∈E(G)uv \in E(G). Let SvS_v be a γve(G−v)\gamma_{\mathrm{ve}}(G-v)-set with cardinality γve(G)−1\gamma_{\mathrm{ve}}(G)-1. We must have u∈Svu \in S_v; otherwise, Sv∪{v}S_v \cup\{v\} is a γve(G)\gamma_{\mathrm{ve}}(G)-set and u∉Sv∪{v}u \notin S_v \cup\{v\}. This contradicts u∈V+(G)u \in V^{+}(G). Since uv∈E(G)uv \in E(G), uu ve-dominates all edges which are incident with vv. Thus, SvS_v is a ve-dominating set of GG. This contradicts v∈V−(G)v \in V^{-}(G). Hence, we have d(u,v)≥2d(u,v) \ge2.

To see the sharpness of the bound, consider the graph in Figure 1(a), where γve(G)=2\gamma_{\mathrm{ve}}(G)=2, γve(G−u)=3\gamma_{\mathrm{ve}}(G-u)=3, and γve(G−v)=1\gamma_{\mathrm{ve}}(G-v)=1. Thus u∈V+(G)u \in V^{+}(G), v∈Vfree−(G)v \in V_{\mathrm{free}}^{-}(G), and d(u,v)=2d(u,v)=2.

Figure 1. (a) u∈V+(G)u \in V^{+}(G) and v∈V−(G)v \in V^{-}(G) with d(u,v)=2d(u,v)=2. (b) u,v∈V+(G)u,v \in V^{+}(G).

:::

The following is an immediate consequence of Theorem 2.13.

Corollary 2.14. Let GG be a graph and v∈V+(G)v \in V^{+}(G). Then N(v)⊆V+(G)∪V0(G)N(v) \subseteq V^{+}(G) \cup V^{0}(G).

The conclusion of Corollary 2.14 cannot be strengthened to N(v)⊆V0(G)N(v) \subseteq V^{0}(G). Indeed, in the graph GG in Figure 1(b), uu and vv are adjacent and γve(G)=2\gamma_{ve}(G) = 2, whereas γve(G−u)=γve(G−v)=3\gamma_{ve}(G-u) = \gamma_{ve}(G-v) = 3.

On vertices in V0(G)V^{0}(G)

We now study vertices whose removal preserves the veve-domination number.

Observation 2.15. Let GG be a graph. Then V0(G)=Vfix0(G)∪Vfree0(G)∪Vbad(G)V^{0}(G) = V_{\mathrm{fix}}^{0}(G) \cup V_{\mathrm{free}}^{0}(G) \cup V_{\mathrm{bad}}(G).

Proof. By Proposition 2.6(1) and Proposition 2.8, V−(G)⊆Vfree(G)V^{-}(G) \subseteq V_{\mathrm{free}}(G) and V+(G)⊆Vfix(G)V^{+}(G) \subseteq V_{\mathrm{fix}}(G). Hence Vbad(G)⊆V0(G)V_{\mathrm{bad}}(G) \subseteq V^{0}(G). Intersecting the partition V(G)=Vfix(G)∪Vfree(G)∪Vbad(G)V(G) = V_{\mathrm{fix}}(G) \cup V_{\mathrm{free}}(G) \cup V_{\mathrm{bad}}(G) with V0(G)V^{0}(G) gives the desired equality.

The graph in Figure 2 shows that a fixed vertex need not belong to V+(G)V^{+}(G). Indeed, {v}\{v\} is the unique γve(G)\gamma_{ve}(G)-set, while G−v≅P5G-v \cong P_{5} and γve(G−v)=γve(G)=1\gamma_{ve}(G-v) = \gamma_{ve}(G) = 1. Hence v∈Vfix0(G)v \in V_{\mathrm{fix}}^{0}(G).

Figure 2. A graph GG with v∈Vfix0(G)v \in V_{\mathrm{fix}}^{0}(G).

Theorem 2.16. Let GG be a graph and v∈V(G)v \in V(G). Then v∈V0(G)v \in V^{0}(G) if and only if one of the following holds:

(1) v∈Vbad(G)v \in V_{\mathrm{bad}}(G);

(2) there exists a γve(G)\gamma_{ve}(G)-set SS containing vv such that ρS(v,R)≥∣R∣+1\rho_{S}(v,R) \geq|R| + 1 for every R⊆S∖{v}R \subseteq S \setminus\{v\}, with equality for at least one such $R.

Proof. Suppose that v∈V0(G)v \in V^{0}(G). If v∈Vbad(G)v \in V_{\mathrm{bad}}(G), then (1) holds. Otherwise, there exists a γve(G)\gamma_{ve}(G)-set SS containing vv. By Lemma 2.9, we have

min⁡R⊆S∖{v}(ρS(v,R)−∣R∣)=γve(G−v)−γve(G)+1=1.\min_{R \subseteq S \setminus\{v\}} \left(\rho_{S}(v,R) - |R|\right) = \gamma_{ve}(G-v) - \gamma_{ve}(G) + 1 = 1.

Hence, ρS(v,R)≥∣R∣+1\rho_{S}(v,R) \geq|R| + 1 for every R⊆S∖{v}R \subseteq S \setminus\{v\}, with equality for at least one such $R. Conversely, by Observation 2.15, we have Vbad(G)⊆V0(G)V_{\mathrm{bad}}(G) \subseteq V^{0}(G). Now suppose that (2) holds. Then

min⁡R⊆S∖{v}(ρS(v,R)−∣R∣)=1.\min_{R\subseteq S\setminus\{v\}}\left(\rho_{S}(v,R)-|R|\right)=1.

By Lemma 2.9, γve(G−v)=γve(G)\gamma_{ve}(G-v)=\gamma_{ve}(G). Thus v∈V0(G)v\in V^{0}(G).

Proposition 2.17. Let GG be a graph and v∈V(G)v\in V(G).

(1) If v∈V0(G)v\in V^{0}(G), then ⋃k≥2Vfixk(G)⊆Vfix(G−v)\bigcup_{k\geq2}V_{\mathrm{fix}}^{k}(G)\subseteq V_{\mathrm{fix}}(G-v).

(2) If v∈Vfree0(G)∪Vbad(G)v\in V_{\mathrm{free}}^{0}(G)\cup V_{\mathrm{bad}}(G), then Vfix(G)⊆Vgood(G−v)V_{\mathrm{fix}}(G)\subseteq V_{\mathrm{good}}(G-v).

(3) If v∈Vbad(G)v\in V_{\mathrm{bad}}(G), then V−(G)⊆V−(G−v)V^{-}(G)\subseteq V^{-}(G-v) and, for every u∈NG(v)u\in N_{G}(v), u∉V−(G−v)u\notin V^{-}(G-v).

Proof. (1) Let u∈Vfixk(G)u\in V_{\mathrm{fix}}^{k}(G) for some k≥2k\geq2, and SS be any γve(G−v)\gamma_{ve}(G-v)-set. Since v∈V0(G)v\in V^{0}(G), ∣S∣=γve(G−v)=γve(G)|S|=\gamma_{ve}(G-v)=\gamma_{ve}(G). Suppose that u∉Su\notin S. Then S∪{v}S\cup\{v\} is a veve-dominating set of G−uG-u. Hence,

γve(G−u)≤∣S∪{v}∣≤γve(G)+1.\gamma_{ve}(G-u)\leq|S\cup\{v\}|\leq\gamma_{ve}(G)+1.

On the other hand, since u∈Vfixk(G)u\in V_{\mathrm{fix}}^{k}(G),

γve(G−u)=γve(G)+k≥γve(G)+2,\gamma_{ve}(G-u)=\gamma_{ve}(G)+k\geq\gamma_{ve}(G)+2,

a contradiction. Thus u∈Su\in S. Since SS is arbitrary, u∈Vfix(G−v)u\in V_{\mathrm{fix}}(G-v).

(2) Let v∈Vfree0(G)∪Vbad(G)v\in V_{\mathrm{free}}^{0}(G)\cup V_{\mathrm{bad}}(G). Then there exists a γve(G)\gamma_{ve}(G)-set SS such that v∉Sv\notin S. By Observation 2.7, SS is a veve-dominating set of G−vG-v. Moreover, ∣S∣=γve(G)=γve(G−v)|S|=\gamma_{ve}(G)=\gamma_{ve}(G-v), and hence SS is a γve(G−v)\gamma_{ve}(G-v)-set. Since every vertex in Vfix(G)V_{\mathrm{fix}}(G) belongs to SS, it follows that Vfix(G)⊆Vgood(G−v)V_{\mathrm{fix}}(G)\subseteq V_{\mathrm{good}}(G-v).

(3) Let v′∈V−(G)v'\in V^{-}(G) and SS be a γve(G−v′)\gamma_{ve}(G-v')-set. Since v∈Vbad(G)v\in V_{\mathrm{bad}}(G), by Proposition 2.6(2), we have v∈Vbad(G−v′)v\in V_{\mathrm{bad}}(G-v'), so v∉Sv\notin S. Thus, SS is a veve-dominating set of G−{v′,v}G-\{v',v\}. Therefore,

γve(G−{v′,v})≤∣S∣=γve(G)−1=γve(G−v)−1.\gamma_{ve}(G-\{v',v\})\leq|S|=\gamma_{ve}(G)-1=\gamma_{ve}(G-v)-1.

Thus v′∈V−(G−v)v'\in V^{-}(G-v). Hence, V−(G)⊆V−(G−v)V^{-}(G)\subseteq V^{-}(G-v).

Now suppose that u∈NG(v)∩V−(G−v)u\in N_{G}(v)\cap V^{-}(G-v), and let S′S' be a γve(G−{u,v})\gamma_{ve}(G-\{u,v\})-set. Since uv∈E(G)uv\in E(G), the vertex vv veve-dominates every edge incident with uu or vv, so S′∪{v}S'\cup\{v\} veve-dominates GG. Moreover, since v∈Vbad(G)⊆V0(G)v\in V_{\mathrm{bad}}(G)\subseteq V^{0}(G),

∣S′∪{v}∣=γve(G−{u,v})+1=γve(G−v)=γve(G).|S'\cup\{v\}|=\gamma_{ve}(G-\{u,v\})+1=\gamma_{ve}(G-v)=\gamma_{ve}(G).

Thus S′∪{v}S'\cup\{v\} is a γve(G)\gamma_{ve}(G)-set, contradicting v∈Vbad(G)v\in V_{\mathrm{bad}}(G). Hence, u∉V−(G−v)u\notin V^{-}(G-v) for every u∈NG(v)u\in N_{G}(v).

The following theorem extends the private-edge bound in [11 Proposition 2] to fixed vertices without assuming that the minimum veve-dominating set is unique. It also yields the counting bound in Corollary 2.19.

Theorem 2.18. Let GG be a graph. For each v∈Vfix(G)v \in V_{\mathrm{fix}}(G), let SvS_v be a γve(G)\gamma_{ve}(G)-set and

Xv={x∈NG(v):x is an endvertex of some e∈peG[v,Sv]∩E(G−v)}.X_v = \{x \in N_G(v) : x\text{ is an endvertex of some }e \in pe_G[v,S_v] \cap E(G-v)\}.

Then Xv⊆V0(G)∖Vfix0(G)X_v \subseteq V^0(G) \setminus V^0_{\mathrm{fix}}(G) and ∣Xv∣≥max⁡{2,γve(G−v)−γve(G)+1}|X_v| \ge\max\{2,\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\}. Moreover, the sets XvX_v are pairwise disjoint.

Proof. We first show that ∣Xv∣≥max⁡{2,γve(G−v)−γve(G)+1}|X_v| \ge\max\{2,\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\}. Since v∈Vfix(G)v \in V_{\mathrm{fix}}(G), v∈Svv \in S_v. If Xv=∅X_v = \varnothing, then every private edge of vv with respect to SvS_v is incident with vv. Hence, Sv∖{v}S_v \setminus\{v\} is a veve-dominating set of G−vG-v. Thus v∈V−(G)v \in V^{-}(G), and by Proposition 2.6(1), v∈Vfree(G)v \in V_{\mathrm{free}}(G), which contradicts v∈Vfix(G)v \in V_{\mathrm{fix}}(G). If ∣Xv∣=1|X_v| = 1, write Xv={x}X_v = \{x\}. Then every edge in peG[v,Sv]∩E(G−v)pe_G[v,S_v] \cap E(G-v) is incident with xx. Moreover, since x∈NG(v)x \in N_G(v), the vertex xx also veve-dominates every private edge of $v that is incident with vv. Thus, xx veve-dominates every edge in peG[v,Sv]pe_G[v,S_v]. Every edge outside peG[v,Sv]pe_G[v,S_v] is veve-dominated by some vertex of Sv∖{v}S_v \setminus\{v\}. Therefore, (Sv∖{v})∪{x}(S_v \setminus\{v\}) \cup\{x\} is a veve-dominating set of GG. Since x≠vx \ne v is an endvertex of a private edge of vv with respect to SvS_v, we have x∉Svx \notin S_v. Thus (Sv∖{v})∪{x}(S_v \setminus\{v\}) \cup\{x\} is a γve(G)\gamma_{ve}(G)-set not containing vv, contradicting v∈Vfix(G)v \in V_{\mathrm{fix}}(G). Therefore, ∣Xv∣≥2|X_v| \ge2.

Moreover, XvX_v veve-dominates every private edge of vv that remains in G−vG-v. Thus, (Sv∖{v})∪Xv(S_v \setminus\{v\}) \cup X_v is a veve-dominating set of G−vG-v, and γve(G−v)≤γve(G)−1+∣Xv∣\gamma_{ve}(G-v) \le\gamma_{ve}(G)-1+|X_v|. It follows that ∣Xv∣≥γve(G−v)−γve(G)+1|X_v| \ge\gamma_{ve}(G-v)-\gamma_{ve}(G)+1.

We next prove that Xv⊆V0(G)∖Vfix0(G)X_v \subseteq V^0(G) \setminus V^0_{\mathrm{fix}}(G). Let x∈Xvx \in X_v. If x∈V−(G)x \in V^{-}(G), then v∈NG(x)v \in N_G(x), and Proposition 2.6(2) and (3) gives v∈Vbad(G−x)∩Vfix(G−x)v \in V_{\mathrm{bad}}(G-x) \cap V_{\mathrm{fix}}(G-x), a contradiction. Hence x∉V−(G)x \notin V^{-}(G). Suppose that x∈Vfix(G)x \in V_{\mathrm{fix}}(G). Then x∈Svx \in S_v. By the definition of XvX_v, there exists an edge e∈peG[v,Sv]∩E(G−v)e \in pe_G[v,S_v] \cap E(G-v) incident with xx. Thus, xx veve-dominates ee, contradicting the fact that ee is a private edge of vv with respect to SvS_v. Hence x∉Vfix(G)x \notin V_{\mathrm{fix}}(G), and therefore x∉V+(G)x \notin V^{+}(G). Thus Xv⊆V0(G)∖Vfix0(G)X_v \subseteq V^0(G) \setminus V^0_{\mathrm{fix}}(G).

Finally, let u,v∈Vfix(G)u,v \in V_{\mathrm{fix}}(G) be distinct and suppose that x∈Xu∩Xvx \in X_u \cap X_v. Since x∈Xvx \in X_v, there exists an edge e∈peG[v,Sv]∩E(G−v)e \in pe_G[v,S_v] \cap E(G-v) incident with xx. Since u∈Vfix(G)u \in V_{\mathrm{fix}}(G), we have u∈Sv∖{v}u \in S_v \setminus\{v\} for any choice of SvS_v. Moreover, x∈Xu⊆NG(u)x \in X_u \subseteq N_G(u), so uu veve-dominates ee, contradicting e∈peG[v,Sv]e \in pe_G[v,S_v]. Hence Xu∩Xv=∅X_u \cap X_v = \varnothing, and the sets XvX_v are pairwise disjoint. □\square

Corollary 2.19. For every graph GG,

∣V0(G)∣≥3∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1).|V^0(G)| \ge3|V^0_{\mathrm{fix}}(G)| + \sum_{v \in V^{+}(G)} \left(\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\right).

In particular,

∣V0(G)∣≥3∣Vfix0(G)∣+2∣V+(G)∣and∣Vfix(G)∣≤∣V(G)∣−∣V−(G)∣3.|V^{0}(G)| \ge3|V_{\mathrm{fix}}^{0}(G)| + 2|V^{+}(G)| \quad\text{and} \quad|V_{\mathrm{fix}}(G)| \le\frac{|V(G)|-|V^{-}(G)|}{3}.

Proof. By Theorem 2.18, the sets XvX_v, v∈Vfix(G)v \in V_{\mathrm{fix}}(G), are pairwise disjoint and satisfy

⋃v∈Vfix(G)Xv⊆V0(G)∖Vfix0(G).\bigcup_{v \in V_{\mathrm{fix}}(G)} X_v \subseteq V^{0}(G) \setminus V_{\mathrm{fix}}^{0}(G).

Moreover, ∣Xv∣≥2|X_v| \ge2 for every v∈Vfix0(G)v \in V_{\mathrm{fix}}^{0}(G), while ∣Xv∣≥γve(G−v)−γve(G)+1|X_v| \ge\gamma_{ve}(G-v)-\gamma_{ve}(G)+1 for every v∈V+(G)v \in V^{+}(G). Since Vfix(G)=Vfix0(G)∪V+(G)V_{\mathrm{fix}}(G)=V_{\mathrm{fix}}^{0}(G)\cup V^{+}(G), we obtain

∣V0(G)∣−∣Vfix0(G)∣≥∑v∈Vfix(G)∣Xv∣=∑v∈Vfix0(G)∣Xv∣+∑v∈V+(G)∣Xv∣≥2∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1).\begin{aligned} |V^{0}(G)|-|V_{\mathrm{fix}}^{0}(G)| &\ge\sum_{v\in V_{\mathrm{fix}}(G)}|X_v|\\ &=\sum_{v\in V_{\mathrm{fix}}^{0}(G)}|X_v|+\sum_{v\in V^{+}(G)}|X_v|\\ &\ge2|V_{\mathrm{fix}}^{0}(G)|+\sum_{v\in V^{+}(G)}\left(\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\right). \end{aligned}

This proves ∣V0(G)∣≥3∣Vfix0(G)∣+∑v∈V+(G)(γve(G−v)−γve(G)+1)|V^{0}(G)|\ge3|V_{\mathrm{fix}}^{0}(G)|+\sum_{v\in V^{+}(G)}\left(\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\right). Since γve(G−v)−γve(G)≥1\gamma_{ve}(G-v)-\gamma_{ve}(G)\ge1 for every v∈V+(G)v\in V^{+}(G), we have

∣V0(G)∣≥3∣Vfix0(G)∣+2∣V+(G)∣.|V^{0}(G)|\ge3|V_{\mathrm{fix}}^{0}(G)|+2|V^{+}(G)|.

Since Vfix(G)V_{\mathrm{fix}}(G) is the disjoint union of Vfix0(G)V_{\mathrm{fix}}^{0}(G) and V+(G)V^{+}(G), we obtain

∣V(G)∣−∣V−(G)∣=∣V0(G)∣+∣V+(G)∣≥3∣Vfix0(G)∣+3∣V+(G)∣=3∣Vfix(G)∣.\begin{aligned} |V(G)|-|V^{-}(G)| &=|V^{0}(G)|+|V^{+}(G)|\\ &\ge3|V_{\mathrm{fix}}^{0}(G)|+3|V^{+}(G)|\\ &=3|V_{\mathrm{fix}}(G)|. \end{aligned}

□

Corollary 2.19 yields the following characterization of CVRve\mathit{CVR}_{ve}.

Corollary 2.20. Let GG be a graph. Then γve(G)≠γve(G−v)\gamma_{ve}(G)\ne\gamma_{ve}(G-v) for every v∈V(G)v\in V(G) if and only if V(G)=V−(G)V(G)=V^{-}(G).

Proof. If V(G)=V−(G)V(G)=V^{-}(G), then γve(G)≠γve(G−v)\gamma_{ve}(G)\ne\gamma_{ve}(G-v) for every v∈V(G)v\in V(G). Suppose that V0(G)=∅V^{0}(G)=\varnothing. Then by Corollary 2.19, we have 0=∣V0(G)∣≥2∣V+(G)∣0=|V^{0}(G)|\ge2|V^{+}(G)|. So V+(G)=∅V^{+}(G)=\varnothing. Since V(G)=V−(G)∪V+(G)∪V0(G)V(G)=V^{-}(G)\cup V^{+}(G)\cup V^{0}(G), V(G)=V−(G)V(G)=V^{-}(G).

It follows from Corollary 2.5 and Corollary 2.20 that G∈CVRveG \in\mathcal{CVR}_{ve} if and only if for all v∈V(G)v \in V(G), there exists a γve(G)\gamma_{ve}(G)-set SS such that v∈Sv \in S and peG[v,S]⊆{uv:u∈NG(v)}pe_G[v,S] \subseteq\{uv:u \in N_G(v)\}, where peG[v,S]≠∅pe_G[v,S] \ne\emptyset.

Corollary 2.20 also implies that V0(G)=∅V^{0}(G)=\emptyset only if V+(G)=∅V^{+}(G)=\emptyset. The converse does not hold. For example, if G=K1,nG=K_{1,n} with n≥2n \ge2, then V+(G)=∅V^{+}(G)=\emptyset, whereas V0(G)≠∅V^{0}(G)\ne\emptyset. We next show that V0(T)≠∅V^{0}(T)\ne\emptyset for every tree TT of order at least three.

Theorem 2.21. For any tree TT on n≥3n \ge3 vertices, V0(T)≠∅V^{0}(T)\ne\emptyset.

Proof. Let vv be the neighbor of an endvertex of a longest path of TT. Then d(v)≥2d(v)\ge2, and vv is adjacent to at least one leaf and at most one non-leaf vertex. If vv has no non-leaf neighbor, then TT is a star. In this case, removing any leaf does not change the veve-domination number, and hence V0(T)≠∅V^{0}(T)\ne\emptyset. Thus, we may assume that N(v)={u1,…,uk,w}N(v)=\{u_1,\ldots,u_k,w\}, where k≥1k\ge1, the vertices u1,…,uku_1,\ldots,u_k are leaves, and ww is a non-leaf vertex.

Suppose that k≥2k\ge2. Fix i∈{1,…,k}i \in\{1,\ldots,k\} and let SS be a γve(T−ui)\gamma_{ve}(T-u_i)-set. Since there exists j≠ij\ne i, the edge vujvu_j must be veve-dominated by some vertex of SS, and hence S∩N[v]≠∅S\cap N[v]\ne\emptyset. Therefore, SS also veve-dominates the edge vuivu_i, so SS is a veve-dominating set of TT. Thus, γve(T)≤γve(T−ui)\gamma_{ve}(T)\le\gamma_{ve}(T-u_i). Since d(ui)=1d(u_i)=1, Theorem 2.1 gives γve(T−ui)≤γve(T)\gamma_{ve}(T-u_i)\le\gamma_{ve}(T). Hence γve(T−ui)=γve(T)\gamma_{ve}(T-u_i)=\gamma_{ve}(T), and therefore ui∈V0(T)u_i\in V^{0}(T).

Now suppose that k=1k=1. Then vv is adjacent to exactly one leaf u1u_1 and d(v)=2d(v)=2. Since d(u1)=1d(u_1)=1, γve(T−u1)≤γve(T)\gamma_{ve}(T-u_1)\le\gamma_{ve}(T). In addition, by Theorem 2.1, γve(T)≤γve(T−u1)+1\gamma_{ve}(T)\le\gamma_{ve}(T-u_1)+1. Hence, we have γve(T−u1)=γve(T)\gamma_{ve}(T-u_1)=\gamma_{ve}(T) or γve(T−u1)=γve(T)−1\gamma_{ve}(T-u_1)=\gamma_{ve}(T)-1. In the first case, u1∈V0(T)u_1\in V^{0}(T). In the second case, u1∈V−(T)u_1\in V^{-}(T). By Theorem 2.13, we have v∉V+(T)v\notin V^{+}(T). If v∈V0(T)v\in V^{0}(T), the conclusion follows. It remains to consider v∈V−(T)v\in V^{-}(T).

Let H=T−{w,v,u1}H=T-\{w,v,u_1\}. Since T−wT-w is the disjoint union of HH and the edge vu1vu_1, γve(T−w)=γve(H)+1\gamma_{ve}(T-w)=\gamma_{ve}(H)+1. A γve(H)\gamma_{ve}(H)-set together with ww veve-dominates TT, so

γve(T)≤γve(H)+1=γve(T−w).\gamma_{ve}(T)\le\gamma_{ve}(H)+1=\gamma_{ve}(T-w).

Thus w∉V−(T)w\notin V^{-}(T). Moreover, since vw∈E(T)vw\in E(T) and v∈V−(T)v\in V^{-}(T), Theorem 2.13 gives w∉V+(T)w\notin V^{+}(T). Hence w∈V0(T)w\in V^{0}(T).

:::

The next result relates the vertices in Vfix0(G)V^{0}_{\mathrm{fix}}(G) to cycles in GG.

Theorem 2.22. Let GG be a graph and v∈V(G)v\in V(G). If v∈Vfix0(G)v\in V^{0}_{\mathrm{fix}}(G), then there exists a cycle CC in GG such that v∈V(C)v\in V(C).

Proof. Let v∈Vfix0(G)v\in V^{0}_{\mathrm{fix}}(G). Since the veve-domination number is additive over components, we may assume that GG is connected. Suppose that there is no cycle containing vv in $G. Since v∈Vfix0(G)v \in V_{\mathrm{fix}}^{0}(G), vv is not isolated. Let N(v)={u1,…,ur}N(v)=\{u_1,\ldots,u_r\}. Then distinct vertices in N(v)N(v) belong to distinct components of G−vG-v; otherwise, there exists a cycle containing vv. Let these components be H1,…,HrH_1,\ldots,H_r, where ui∈V(Hi)u_i \in V(H_i). Then each uiu_i is the only vertex of HiH_i adjacent to vv. For each ii, let

ai=min⁡{∣A∣:A⊆V(Hi) and A∪{v} ve-dominates G[V(Hi)∪{v}]}.a_i=\min\{|A|: A\subseteq V(H_i)\text{ and }A\cup\{v\}\ ve\text{-dominates }G[V(H_i)\cup\{v\}]\}.

Set bi=γve(Hi)b_i=\gamma_{ve}(H_i), and choose Bi∈S(Hi)B_i\in\mathcal{S}(H_i). Since Bi∪{v}B_i\cup\{v\} veve-dominates G[V(Hi)∪{v}]G[V(H_i)\cup\{v\}], we have ai≤∣Bi∣=bia_i\leq|B_i|=b_i. Moreover, since uiu_i is the only vertex of HiH_i adjacent to vv, adding uiu_i suffices to veve-dominate all edges of HiH_i that may be veve-dominated by vv. Thus bi≤ai+1b_i\leq a_i+1. Hence

bi−ai∈{0,1}.(4)b_i-a_i\in\{0,1\}. \tag*{(4)}

Let SS be a γve(G)\gamma_{ve}(G)-set. Since vv is fixed, v∈Sv\in S. For each ii, no vertex of another component of G−vG-v can veve-dominate an edge of HiH_i, so ∣S∩V(Hi)∣≥ai|S\cap V(H_i)|\geq a_i. Conversely, if AiA_i attains aia_i for each ii, then {v}∪⋃i=1rAi\{v\}\cup\bigcup_{i=1}^{r}A_i veve-dominates GG. Hence

γve(G)=1+∑i=1rai.(5)\gamma_{ve}(G)=1+\sum_{i=1}^{r}a_i. \tag*{(5)}

On the other hand,

γve(G−v)=∑i=1rbi.(6)\gamma_{ve}(G-v)=\sum_{i=1}^{r}b_i. \tag*{(6)}

Since v∈Vfix0(G)v\in V_{\mathrm{fix}}^{0}(G), γve(G−v)=γve(G)\gamma_{ve}(G-v)=\gamma_{ve}(G).

By (4)–(6), we have ∑i=1r(bi−ai)=1\sum_{i=1}^{r}(b_i-a_i)=1. Hence, there is a unique index jj such that bj=aj+1b_j=a_j+1, while bi=aib_i=a_i for every i≠ji\ne j. Choose AjA_j attaining aja_j, and for each i≠ji\ne j, choose Bi∈S(Hi)B_i\in\mathcal{S}(H_i). Then Aj∪{uj}A_j\cup\{u_j\} is a veve-dominating set of HjH_j. We have uj∉Aju_j\notin A_j; otherwise, AjA_j would veve-dominate HjH_j, contradicting bj=aj+1b_j=a_j+1. Since ∣Aj∪{uj}∣=aj+1=bj|A_j\cup\{u_j\}|=a_j+1=b_j, the set Aj∪{uj}A_j\cup\{u_j\} is a γve(Hj)\gamma_{ve}(H_j)-set. Let D=(⋃i≠jBi)∪Aj∪{uj}D=\left(\bigcup_{i\ne j}B_i\right)\cup A_j\cup\{u_j\}. Then DD veve-dominates every edge of G−vG-v. Moreover, since uj∈N(v)u_j\in N(v), the vertex uju_j veve-dominates every edge incident with vv. Therefore, DD is also a veve-dominating set of GG. Furthermore,

∣D∣=∑i=1rbi=γve(G−v)=γve(G),|D|=\sum_{i=1}^{r}b_i=\gamma_{ve}(G-v)=\gamma_{ve}(G),

so DD is a γve(G)\gamma_{ve}(G)-set not containing vv, contradicting v∈Vfix(G)v\in V_{\mathrm{fix}}(G).

Corollary 2.23

Corollary 2.23. For every forest FF, Vfix(F)=V+(F)V_{\mathrm{fix}}(F)=V^{+}(F).

Proof. By Proposition 2.6(1) and Proposition 2.8, Vfix(F)=Vfix0(F)∪V+(F)V_{\mathrm{fix}}(F)=V_{\mathrm{fix}}^0(F)\cup V^+(F). Since FF contains no cycle, Theorem 2.22 gives Vfix0(F)=∅V_{\mathrm{fix}}^0(F)=\varnothing, and the result follows.

This extends the implication (i)⇒\Rightarrow(iii) of [11 Theorem 7] to fixed vertices in arbitrary forests, without assuming that the minimum veve-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)\gamma_{ve}(G-v) and characterized the three vertex classes V−(G)V^-(G), V0(G)V^0(G), and V+(G)V^+(G). We also introduced an exchange parameter, derived a weighted counting bound, and proved that every fixed vertex in V0(G)V^0(G) lies on a cycle.

Our results imply that a nonempty forest FF belongs to CVRve\mathcal{CVR}_{ve} if and only if each component is isomorphic to K2K_2. Indeed, every isolated vertex belongs to V0(F)V^0(F). By Theorem 2.21 and additivity, every component of order at least three also contains a vertex of V0(F)V^0(F). Conversely, if all components are copies of K2K_2, deleting any vertex decreases γve(F)\gamma_{ve}(F) by one.

For paths and cycles, the standard formulas (see Peters [10] and Lewis [7 Proposition 23]) are

γve(Pm)=⌈m−14⌉(m≥1),γve(Cn)=⌈n4⌉(n≥3).\gamma_{ve}(P_m)=\left\lceil\frac{m-1}{4}\right\rceil\quad(m\ge1), \qquad\gamma_{ve}(C_n)=\left\lceil\frac{n}{4}\right\rceil\quad(n\ge3).

Since Cn−v≅Pn−1C_n-v\cong P_{n-1} for every v∈V(Cn)v\in V(C_n), we have Cn∈CVRveC_n\in\mathcal{CVR}_{ve} if and only if n≡1,2(mod4)n\equiv1,2\pmod{4}.

It would be interesting to obtain further structural characterizations of graphs in CVRve\mathcal{CVR}_{ve}, to characterize graphs satisfying V0(G)=V(G)V^0(G)=V(G), and to determine whether the coefficients in the weighted bound of Corollary 2.19 can be improved.

References

  1. [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. [2]R. Boutrig, M. Chellali, T. W. Haynes, S. T. Hedetniemi, Vertex-edge domination in graphs, Aequationes Math. 90 (2016) 355–366.DOI
  3. [3]Y. Caro, A. Hansberg, Partial domination—the isolation number of a graph, Filomat 31 (2017) 3925–3944.DOI
  4. [4]S. K. Jena, G. K. Das, Vertex-edge domination in unit disk graphs, Discrete Appl. Math. 319 (2022) 351–361.
  5. [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. [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. [7]J. R. Lewis, Vertex-Edge and Edge-Vertex Parameters in Graphs, Ph.D. dissertation, Clemson University, 2007.
  8. [8]J. R. Lewis, S. T. Hedetniemi, T. W. Haynes, G. H. Fricke, Vertex-edge domination, Util. Math. 81 (2010) 193–213.
  9. [9]S. Paul, K. Ranjan, Results on vertex-edge and independent vertex-edge domination, J. Comb. Optim. 44 (2022) 303–330.DOI
  10. [10]K. W. Peters, Theoretical and Algorithmic Results on Domination and Connectivity, Ph.D. dissertation, Clemson University, 1986.
  11. [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. [12]D. K. Thakkar, N. P. Jamvecha, About ve-domination in graphs, Ann. Pure Appl. Math. 14 (2017) 245–250.DOI
  13. [13]R. Ziemann, P. Żyliński, Vertex-edge domination in cubic graphs, Discrete Math. 343 (2020) 112075.DOI
  14. [14]P. Żyliński, Vertex-edge domination in graphs, Aequationes Math. 93 (2019) 735–742.DOI

Paper details

vlnc:W_58gda2an
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents