MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION PROBLEMS FOR TWISTED CUBES

ABSTRACT. The matching preclusion number of a graph is the mini-mum number of edges whose deletion results in a graph that has nei-ther perfect matchings nor almost. perfect matchings. For many inter-connection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper, we find the matching preclusion number and the condi· tional matching preclusion number for twisted cubes, an improved version of the well-known hypercube. Moreover, we also classify all the optimal matching preclusion sets