Two Results on the Binding Numbers of Product Graphs

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) \neq V(G) \). In this paper, two general results for the binding numbers of product graphs are obtained. (1) For any \(G \) on \(m \) vertices, it is shown that \( bind (G \times K_n) = \frac{nm-1}{nm-\delta(G)-n+1} \) for all \(n \) sufficiently large.(2) For arbitrary \(G \) and for \(H \) with \( bind(H) \geq 1 \), a (relatively) simple expression is derived for \( bind (G[H]) \).