A Characterization of Trees in Which No Edge is Essential to the Domination Number

Bert L. Hartnell1, Douglas F. Rall2
1 Department of Mathematics and Computing Science Saint Mary’s University Halifax, Nova Scotia Canada B3H 3C3
2Department of Mathematics Furman University Greenville, South Carolina 29613 U.S.A.

Abstract

For any tree \(T\), let \(\gamma(T)\) represent the size of a minimum dominating set. Let \({E}_0\) represent the collection of trees with the property that, regardless of the choice of edge \(e\) belonging to the tree \(T\), \(\gamma(T – e) = \gamma(T)\). We present a constructive characterization of \({E}_0\).