2017/09/13 by Lin, Ruizhi, Zhang, Heping
#05C72 #90C27 #90C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1709.04188
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 programming which can be used to find matching preclusion number of graphs. In this paper, by relaxing of the 0-1 linear programming we obtain a linear programming and call its optimal objective value as fractional matching preclusion number of graph G, denoted by mpf(G). We show mpf(G) can be computed in polynomial time for any graph G. By using perfect matching polytope, we transform it as a new linear programming whose optimal value equals the reciprocal of mpf(G). For bipartite graph G, we obtain an explicit formula for mpf(G) and show that \lfloor mpf(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 mpf(G \square H) \geqslant mpf(G)+\lfloor mpf(H) \rfloor, where G \square H is the Cartesian product of G and H.