The Binding Number of Trees and $K(1,3)$-free Graphs

Abstract

The binding number of a graph $G$ is defined to be the minimum of $|N(S)|/|S|$ taken over all nonempty $S\subseteq V(G)$ such that $N(S)\ne V(G)$. In this paper, another look is taken at the basic properties of the binding number. Several bounds are established, including ones linking the binding number of a tree to the “distribution” of its end-vertices. Further, it is established that under some simple conditions, $K_{1,3}$-free graphs have binding number equal to $(p(G)–1)/(p(G)–\delta (G))$ and applications of this are considered.