A characterization of trees having a minimum vertex cover which is also a minimum total dominating set

Abstract

A vertex cover of a graph $G=(V,E)$ is a set $X\subseteq V$ such that each edge of $G$ is incident to at least one vertex of $X$. A dominating set $D\subseteq V$ is a total dominating set of $G$ if the subgraph induced by $D$ has no isolated vertices. A $({\gamma }_t-\tau )$-set of $G$ is a minimum vertex cover which is also a minimum total dominating set. In this article we give a constructive characterization of trees having a $({\gamma }_t-\tau )$-set.

15 pages, 2, figures