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.