On anti-Kekulé and s-restricted matching preclusion problems

The anti-Kekulé number of a connected graph G is the smallest number of edges whose deletion results in a connected subgraph having no Kekulé structures (perfect matchings). As a common generalization of (conditional) matching preclusion number and anti-Kekulé number of a graph G, we introduce s-restricted matching preclusion number 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s+1$$\end{document} vertices. In this paper, we first show that conditional matching preclusion problem and anti-Kekulé problem are NP-complete, respectively, then generalize this result to s-restricted matching preclusion 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.