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 ) ⩾ − 1 2 k 2 + ( 2 n − 3 2 ) k − ( n 2 − 2 ) for each n...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2006-02, Vol.97 (3), p.88-93
Main Authors: Yang, Xiaofan, Cao, Jianqiu, Megson, Graham M., Luo, Jun
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Generalized cube
Graph theory
Graphs
Hypercube
Interconnect
Interconnection networks
Mathematics
Minimum neighborhood problem
Network topologies
Sciences and techniques of general use
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ) ⩾ − 1 2 k 2 + ( 2 n − 3 2 ) k − ( n 2 − 2 ) for each n-dimensional generalized cube and each integer k satisfying n + 2 ⩽ k ⩽ 2 n . 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].
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2005.10.003