Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes

被引：51
作者：
Li, Hao [2 ,3 ]
Yang, Weihua [1 ,2 ]
机构：
[1] Taiyuan Univ Technol, Dept Math, Taiyuan 030024, Shanxi, Peoples R China
[2] Univ Paris 11, CNRS, UMR 8623, Lab Rech Informat, F-91405 Orsay, France
[3] Jianghan Univ, Inst Interdisciplinary Res, Wuhan 430056, Hubei, Peoples R China
来源：
DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 16-17期
基金：
中国国家自然科学基金;
关键词：
Hypercube; n-cube; Extra edge-connectivity; GENERALIZED MEASURES; FAULT-TOLERANCE; NETWORKS; RELIABILITY; CYCLES;
D O I：
10.1016/j.dam.2013.04.009
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this note, we show that a subgraph induced by m (denote m by Sigma(s)(i=0) 2(ti), t(0) = [log(2) m] and ti = [log(2) (m - Sigma(i-1)(r=0) 2(tr))] for i >= 1) vertices of an n-dimensional hypercube has at most Sigma(s)(i=0) t(i)2(t-1) + Sigma(s)(i=0) i . 2(ti) edges. As an application, we determine the m-extra edge-connectivity of hypercubes for m <= 2([n/2]). (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：2753 / 2757
页数：5
相关论文
共 15 条
12