Fractional Matching Preclusion for (Burnt) Pancake Graphs

摘要

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has no perfect matchings or almost perfect matchings. As a generalization, Liu and Liu [20] introduced the fractional matching preclusion number, defined as the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number of G is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching. In this paper, we obtain the fractional matching preclusion number and the fractional strong matching preclusion number for pancake graphs and burnt pancake graphs and classify all optimal preclusion sets of these graphs.