Total vertex-edge domination in trees

Abstract

A subset $S\subseteq V$ is a dominating set of $G$ if every vertex in $V\setminus S$ has a neighbor in $S$ and it is a total dominating set if every vertex in $V$ has a neighbor in $S$. The total domination number of $G$%, $\gamma _{t}(G)$, is the minimum cardinality of a total dominating set of $G$. A vertex $v$ of a graph $G$ is said to $ve$-dominate every edge incident to $v$, as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is a vertex-edge dominating set (or simply, a $ve$-dominating set) if every edge of $E$ is $ve$-dominated by at least one vertex of $S$. A total $ve$-dominating set of $G$ is a $ve$-dominating setwhose induced subgraph has no isolated vertex. The vertex-edge domination number $\gamma _{ve}(G)$ is the minimum cardinality of a total $ve$-dominating set and the total vertex-edge domination number $\gamma_{ve}^{t}(G)$ is the minimum cardinality of a total $ve$-dominating set in $G $. In this paper, we characterize all trees $T$ with $\gamma_{ve}^{t}(T)=\gamma _{t}(T)$ or $\gamma _{ve}^{t}(T)=\gamma_{ve}(T)$, answering two open problems posed in [Boutrig and Chellali, Total vertex-edge domination, Int. J. Comput. Math. 95 (2018), 1820--1828]. Moreover, we show that it is NP-hard to decide whether $\gamma _{ve}^{t}(G)=\gamma _{ve}(G)$ for a given connected $(K_{4}-e)$-free graph $G$.