A characterization of trees having a minimum vertex cover which is also a minimum total dominating set
Preprint
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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- A characterization of trees with equal 2-domination and 2-independence numbersDiscrete Mathematics & Theoretical Computer Science, 2017
- A characterization of trees with equal independent domination and secure domination numbersInformation Processing Letters, 2017
- Edge dominating sets and vertex coversDiscussiones Mathematicae Graph Theory, 2013
- A survey of selected recent results on total domination in graphsDiscrete Mathematics, 2009
- Construction of trees and graphs with equal domination parametersDiscrete Mathematics, 2006
- An efficient simulated annealing algorithm for the minimum vertex cover problemNeurocomputing, 2006
- Characterizations of trees with equal domination parametersJournal of Graph Theory, 2000
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- A characterization of graphs in which some minimum dominating set covers all the edgesCzechoslovak Mathematical Journal, 1995
- A constructive characterization of trees with at least k disjoint maximum matchingsJournal of Combinatorial Theory, Series B, 1978