The restricted h-connectivity of balanced hypercubes

2018/05/22 by Lü, Huazhong, Wu, Tingzeng
#05C40 #68R10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1805.08461

Abstract

The restricted h-connectivity of a graph G, denoted by κ^h(G), is defined as the minimum cardinality of a set of vertices F in G, if exists, whose removal disconnects G and the minimum degree of each component of G-F is at least h. In this paper, we study the restricted h-connectivity of the balanced hypercube BH_n and determine that κ¹(BH_n)=κ²(BH_n)=4n-4 for n≥2. We also obtain a sharp upper bound of κ³(BH_n) and κ⁴(BH_n) of n-dimension balanced hypercube for n≥3 (n≠4). In particular, we show that κ³(BH₃)=κ⁴(BH₃)=12.

Related

• Structure and substructure connectivity of balanced hypercubes
• The g-extra edge-connectivity of balanced hypercubes
• Structure connectivity and substructure connectivity of twisted hypercubes
• P_k and C_k structure and substructure connectivity of hypercubes
• The generalized 3-connectivity of the folded hypercube FQ_n