Minimum neighborhood in a generalized cube

Generalized cubes are a subclass of hypercube-like networks, which include some hypercube variants as special cases. Let θG(k) denote the minimum number of nodes adjacent to a set of k vertices of a graph G. In this paper, we prove θG(k)⩾−12k2+(2n−32)k−(n2−2) for each n-dimensional generalized cube and each integer k satisfying n+2⩽k⩽2n. Our result is an extension of a result presented by Fan and Lin [J. Fan, X. Lin, The t/k-diagnosability of the BC graphs, IEEE Trans. Comput. 54 (2) (2005) 176–184].