A New Lower Bound for the Irredundance Number of a Tree

Gerd Fricke1, Timothy J.O’Brien1, W.Christopher Schroeder1, Stephen T.Hedetniemi2, Professor Emeritus2
1Department of Mathematics Morehead State University, Morehead, KY 40351
2School of Computing Clemson University, Clemson, SC 29634

Abstract

In this note, we prove that for any tree \( T \), \( \gamma_{\leq2}(T) \leq \gamma_\gamma(T) \leq ir(T) \leq \gamma(T) \), where \( \gamma_{\leq2}(G) \) is the distance-2 domination number, \( ir(T) \) is the (lower) irredundance number, \( \gamma(T) \) is the domination number, and \( \gamma_\gamma(T) \), newly defined here, equals the minimum cardinality of a set of vertices that dominates a minimum dominating set of \( T \).