Binding Number and Tenacity

Abstract

Let $T(G)$ and $\text{bind}(G)$ be the tenacity and the binding number, respectively, of a graph $G$. The inequality $T(G)\ge \text{bind}(G)–1$ was derived by D. Moazzami in [11]. In this paper, we provide a stronger lower bound on $T(G)$ that is best possible when $\text{bind}(G)\ge 1$.