2023/06/02 by Chang, Caibing, Liu, Yan
#05C70 #05C72 #05C99 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.01216
As a generalization of matching preclusion number of a graph, we provide the (strong) integer k-matching preclusion number, abbreviated as MPk number (SMPk number), which is the minimum number of edges (vertices and edges) whose deletion results in a graph that has neither perfect integer k-matching nor almost perfect integer k-matching. In this paper, we show that when k is even, the (SMPk) MPk number is equal to the (strong) fractional matching preclusion number. We obtain a necessary condition of graphs with an almost-perfect integer k-matching and a relational expression between the matching number and the integer k-matching number of bipartite graphs. Thus the MPk number and the SMPk number of complete graphs, bipartite graphs and arrangement graphs are obtained, respectively.