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:
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.