Fractional matching preclusion number of graphs and the perfect matching polytope

作     者：Lin, Ruizhi Zhang, Heping 

作者机构：Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China Fujian Univ Technol Sch Math & Phys Fuzhou 350118 Fujian Peoples R China 

出 版 物：《JOURNAL OF COMBINATORIAL OPTIMIZATION》 (组合优化杂志)

年 卷 期：2020年第39卷第3期

页      面：915-932页

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSFC Foundation of Education Department of Fujian Province [JAT190417] 

主　　题：Graph Perfect matching Matching preclusion Linear program Perfect matching polytope Flow 

摘      要：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 mpf (G). We showmpf (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 mpf (G). For bipartite graph G, we obtain an explicit formula for mpf (G) and show that mpf (G) 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 H) mpf (G) + mpf (H), where G H is the Cartesian product of G and H.