On extra connectivity and extra edge-connectivity of balanced hypercubes

摘要

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 BHn for n ≥ 2 and h≤2n−1. As an application, we prove that κ4(BHn)=κ5(BHn)=6n−8 and λ3(BHn)=8n−8, which improves the previously known results given by Yang (2012) and Lü (2017).