On anti-Kekule and s-restricted matching preclusion problems

The anti-Kekule number of a connected graph G is the smallest number of edges whose deletion results in a connected subgraph having no Kekule structures (perfect match-ings). As a common generalization of (conditional) matching preclusion number and anti-Kekule number of a graph G, we introduce s-restricted matching preclusion num-ber of G as the smallest number of edges whose deletion results in a subgraph without perfect matchings such that each component has at least s +1 vertices. In this paper, we first show that conditional matching preclusion problem and anti-Kekule problem are NP-complete, respectively, then generalize this result to s-restricted matching preclu-sion problem. Moreover, we give some sufficient conditions to compute s-restricted matching preclusion numbers of regular graphs. As applications, s-restricted matching preclusion numbers of complete graphs, hypercubes and hyper Petersen networks are determined.