Matching Preclusion Problem For Generalized Petersen Graphs

In interconnection networks,matching preclusion is a measure of robustness when there is a link failure.The matching preclusion number of an even graph is the minimum number of edges whose deletion results in a graph that has no perfect matching.Many interconnection networks are proved to be maximally matched and super matched.Recently,the conditional matching preclusion number of an even graph was introduced to look for matching preclusion sets beyond those induced by a single vertex.It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has no perfect matchings.In this paper,we study this problem for generalized Petersen graphs (9),6)).We obtain that (9),6))is maximally matched;Also,(9),6))is super matched and conditionally maximally matched except for several small cases.Moreover,we noticed that (9),6))is not conditional super matched when a 3-cycle or 4-cycle or 5-cycle is included in (9),6)),from which we obtain that (9),1)and (9),2)are not conditionally super matched.We also identify all optimal conditional matching preclusion sets of P(n,1),P(n,2).