Accessibility navigation

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

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.ipl.2005.10.003


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
ID Code:15462
Uncontrolled Keywords:interconnection networks, hypercube, generalized cube, minimum, neighborhood problem, MAXIMAL CONNECTED COMPONENT, FAULTY VERTICES, DIAGNOSABILITY, HYPERCUBE, TOPOLOGY, SYSTEMS, NETWORK

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

Page navigation