Fractional matching preclusion number of graphs and the perfect matching polytope

Let G be a graph with an even number of vertices. The matching preclusion number of G, denoted by mp(G), is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching. We introduced a 0–1 linear program which can be used to find the matching preclusion number of graphs. In this paper, by relaxing of the 0–1 linear program we obtain a linear program and call its optimal objective value as fractional matching preclusion number of graph G, denoted by $$mp_f(G)$$. We show $$mp_f(G)$$ can be computed in polynomial time for any graph G. By using the perfect matching polytope, we transform it into a new linear program whose optimal value equals the reciprocal of $$mp_f(G)$$. For bipartite graph G, we obtain an explicit formula for $$mp_f(G)$$ and show that $$\lfloor mp_f(G) \rfloor $$ is the maximum integer k such that G has a k-factor. Moreover, for any two bipartite graphs G and H, we show $$mp_f(G \square H) \geqslant mp_f(G)+\lfloor mp_f(H) \rfloor $$, where $$G \square H$$ is the Cartesian product of G and H.