Edge-Vertex Domination of Acyclic Trapezoid Graphs: Algorithm and Complexity

In an undirected graph $G = (V,E)$, an edge $e \in E(G)$ edge-vertex dominates a node point $w \in V(G)$ if $w$ is incident to $e$ or if $w$ is incident to an adjacent edge of $e$. A subset $S_{EV}$ of $E$ is called an edge-vertex dominating set of $G$ if every node point of $V(G)$ is edge-vertex dominated by at least one edge of $S_{EV}$. The edge-vertex domination number is the minimum cardinality among all edge-vertex dominating sets, we denote it by $ \gamma _{EV}(G)$. In our paper, first we study some properties of acyclic trapezoid graphs. We also describe some properties in connection with edge-vertex dominating set of an acyclic trapezoid graph. Then we propose a linear time algorithm for determining a minimum $S_{EV}$ of acyclic trapezoid graph having $n$ nodes. We also analyze the time and space complexities of our proposed algorithm.