Strong matching preclusion number of graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. The strong matching preclusion number (or simply, SMP number) smp(G) of a graph G is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has been introduced by Park and Ihm. In this paper, we first study the SMP number of some special graph classes, and give some sharp upper and lower bounds of SMP number. Next, graphs with large and small SMP number are characterized, respectively. In the end, we investigate the Nordhaus-Gaddum-type relations on SMP number.