The outer-independent edge-vertex domination in trees

Abstract

Let $G=(V,E)$ be a finite simple graph with vertex set $V=V(G)$ and edge set $E=E(G)$. A vertex $v \in V$ is edge-vertex dominated by an edge $e \in E$ if $e$ is incident with $v$ or $e$ is incident with a vertex adjacent to $v$. An edge-vertex dominating set of $G$ is a subset $D \subseteq E$ such that every vertex of $G$ is edge-vertex dominated by an edge of $D$. A subset $D \subseteq E$ is called an \textit{outer-independent edge-vertex dominating set} of $G$ if $D$ is an edge-vertex dominating set of $G$ and the set $V(G) \setminus I(D)$ is independent, where $I(D)$ is the set of vertices incident to an edge of $D$. The outer-independent edge-vertex domination number of $G$, denoted by $\gamma_{ev}^{oi}(G)$, is the smallest cardinality of an outer-connected edge-vertex dominating set of $G$. In this paper, we initiate the study of outer-independent edge-vertex domination numbers. In particular, we prove that $\frac{n- l +1}{3} \leq \gamma_{ev}^{oi}(T) \leq \frac{2n -s -2}{3}$ for every tree $T$ of order $n \geq 3$ with $l$ leaves and $s$ support vertices. We also characterize the trees attaining each of the bounds.