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.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/15462
Item Type	Article
Refereed	Yes
Divisions	Science
Uncontrolled Keywords	interconnection networks, hypercube, generalized cube, minimum, neighborhood problem, MAXIMAL CONNECTED COMPONENT, FAULTY VERTICES, DIAGNOSABILITY, HYPERCUBE, TOPOLOGY, SYSTEMS, NETWORK
Download/View statistics	View download statistics for this item