Repozytorium publikacji - Politechnika Gdańska

A vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4 \le \gamma_{ve}(T) \le n/3$, and we characterize the trees attaining each of the bounds.

Autorzy

• Balakrishna Krishnakumari,
• Yanamandram B. Venkatakrishnan,
• dr inż. Marcin Krzywkowski link otwiera się w nowej karcie