Accessibility navigation

A lower bound on the size of k-neighborhood in generalized cubes

Yang, X.F., Megson, G.M., Cao, J.Q. and Luo, J. (2006) A lower bound on the size of k-neighborhood in generalized cubes. Applied Mathematics and Computation, 179 (1). pp. 47-54. ISSN 0096-3003

Full text not archived in this repository.

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item DOI: 10.1016/j.ame.2005.11.080


The determination of the minimum size of a k-neighborhood (i.e., a neighborhood of a set of k nodes) in a given graph is essential in the analysis of diagnosability and fault tolerance of multicomputer systems. The generalized cubes include the hypercube and most hypercube variants as special cases. In this paper, we present a lower bound on the size of a k-neighborhood in n-dimensional generalized cubes, where 2n + 1 <= k <= 3n - 2. This lower bound is tight in that it is met by the n-dimensional hypercube. Our result is an extension of two previously known results. (c) 2005 Elsevier Inc. All rights reserved.

Item Type:Article
ID Code:15477
Uncontrolled Keywords:interconnection network, hypercube, generalized cube, k-neighborhood, MAXIMAL CONNECTED COMPONENT, FAULTY VERTICES, DIAGNOSABILITY, HYPERCUBE, TOPOLOGY, SYSTEMS, NETWORK

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation