Minimum neighborhood in a generalized cube

Yang, X.F., Cao, J.Q., Megson, G.M. and Luo, J. (2006) Minimum neighborhood in a generalized cube. Information Processing Letters, 97 (3). pp. 88-93. ISSN 0020-0190 doi: 10.1016/j.ipl.2005.10.003

Abstract/Summary

Generalized cubes are a subclass of hypercube-like networks, which include some hypercube variants as special cases. Let theta(G)(k) denote the minimum number of nodes adjacent to a set of k vertices of a graph G. In this paper, we prove theta(G)(k) >= -1/2k(2) + (2n - 3/2)k - (n(2) - 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]. (c) 2005 Elsevier B.V. All rights reserved.