Component connectivity of the hypercubes

Abstract

Abstract The r-component connectivity κ r (G) of the non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, κ2 is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q n for r=2, 3, …, n+1, and we classify all the corresponding optimal solutions. Keywords: hypercubescomponent connectivity 2010 AMS Subject Classifications : 05C7505C40 Acknowledgements We thank the three anonymous referees for a number of helpful comments and suggestions. Notes The Hamming distance of two binary strings of the same length is the number of bits that they differ.