Bulletin of the
Korean Mathematical Society BKMS

A vertex $v$ of a graph $G=(V,E)$ 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 called a double vertex-edge dominating set if every edge of $E$ is $ve$-dominated by at least two vertices of $S$. The minimum cardinality of a double vertex-edge dominating set of $G$ is the double vertex-edge domination number $\gamma_{dve}(G)$. In this paper, we provide an upper bound on the double vertex-edge domination number of trees in terms of the order $n$, the number of leaves and support vertices, and we characterize the trees attaining the upper bound. Finally, we design a polynomial time algorithm for computing the value of $\gamma_{dve}(T)$ for any trees. This gives an answer of an open problem posed in [4].

Keywords: Double vertex-edge dominating set, trees

MSC numbers: 05C69, 05C35

Supported by: This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2020R1I1A3A04036669).