Vertex Removal and Vertex-Edge Domination

Abstract

A vertex $v$ of a graph $G$ $ve$-dominates every edge incident with a vertex in its closed neighborhood $N_G[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 ${\gamma }_{ve}(G)$, also known as the isolation number. In this paper, we study the effect of vertex removal on ${\gamma }_{ve}(G)$, establish sharp bounds on ${\gamma }_{ve}(G-v)$ and characterize the vertices whose removal decreases, preserves, or increases ${\gamma }_{ve}(G)$. Let $V^0(G)$ and $V^{+}(G)$ denote the sets of vertices whose removal preserves and increases ${\gamma }_{ve}(G)$, respectively, and let $V_{\mathrm{fix}}^0(G)$ consist of the vertices in $V^0(G)$ belonging to every minimum $ve$-dominating set. We prove that \[ |V^0(G)|\geq3|V_{\mathrm{fix}}^0(G)|+\sum_{v\in V^+(G)} \bigl(γ_{ve}(G-v)-γ_{ve}(G)+1\bigr). \] In particular, $|V^0(G)|\ge 2|V^{+}(G)|$. We also prove that every vertex in $V_{\mathrm{fix}}^0(G)$ lies on a cycle and that $V^0(T)\ne \varnothing$ for every tree $T$ of order at least three.