Neighbor connectivity of k-ary n-cubes

10/27/2019

∙

by   Tomáš Dvořák, et al.

∙

0

∙

share

The neighbor connectivity of a graph G is the least number of vertices such that removing their closed neighborhoods from G results in a graph that is disconnected, complete or empty. If a graph is used to model the topology of an interconnection network, this means that the failure of a network node causes failures of all its neighbors. We completely determine the neighbor connectivity of k-ary n-cubes for all n>1 and k>2.