Matching preclusion for k k -ary n n -cubes ?
The (conditional) matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph (with no isolated vertices) that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that the matching preclusion number and the conditional matching preclusion number of the k k -ary n n -cube with even k?4 k ? 4 are 2n 2 n and 4n?2 4 n ? 2 , respectively.
perfect matching almost perfect matching interconnection networks k k -ary n n -cubes k k k k k n n n n n