On extra connectivity and extra edge-connectivity of balanced hypercubes
On extra connectivity and extra edge-connectivity of balanced hypercubes
复制标题
关于平衡超立方体的额外连通性和额外边缘连通性
DOI：
10.1016/j.amc.2017.10.005
复制
发表时间：
2018
影响因子：
4
通讯作者：
Zhou Jin-Xin
中科院分区：
文献类型：
--
作者：
Yang Da-Wei;Feng Yan-Quan;Lee Jaeun;Zhou Jin-Xin
给定一个图G和一个非负整数h，h-额外连通度(或h-额外边连通度，分别为.)分别记为κh(G)(或λh(G))是一组顶点(或边)的最小基数。在G中，如果它存在，它的删除断开了G的连接，并使每个剩余的分支具有超过h个顶点。本文得到了n维平衡超立方体BHn对n≥2和h≤2 n−1的h-额外连通性和h-额外边连通性的一个紧上界.作为应用，我们证明了κ4(BHn)=κ5(BHn)=6 n−8和λ3(BHn)=8 n−8，改进了杨春和L(2017)已有的结果.
Given a graph G and a non-negative integer h, the h-extra connectivity (or h-extra edge-connectivity, resp.) of G, denoted by κ h (G)(or λ h (G), resp.), is the minimum cardinality of a set of vertices (or edges, resp.) in G, if it exists, whose deletion disconnects G and leaves each remaining component with more than h vertices. In this paper, we obtain a tight upper bound of the h-extra connectivity and the h-extra edge-connectivity of n-dimensional balanced hypercubes BH n for n≥ 2 and h≤ 2 n− 1. As an application, we prove that κ 4 (B H n)= κ 5 (B H n)= 6 n− 8 and λ 3 (B H n)= 8 n− 8, which improves the previously known results given by Yang (2012) and Lü (2017).