Matching Preclusion For Radix Triangular Mesh And Butterfly Derived Networks

In graph theory and network analysis,the robustness of a graph or class of graphs measures its resilience to the removal of edges or vertices.Robustness can be formal-ized in a variety of ways,depending on how the edges or vertices to be removed are chosen.Matching exclusion problem is closely related to edge deletion problem in graph theory,and matching exclusion set has important research significance in dis-crete mathematics.The matching preclusion number of a graph G,denoted by mp?G?,is the min-imum number of edges whose deletion leaves the resulting graph without a perfect matching or an almost perfect matching.Furthermore,Cheng et al.introduced the con-cept of conditional matching preclusion.The conditional matching preclusion number of G,denoted by mp₁?G?,is the minimum number of edges whose deletion leaves the resulting graph with no isolated vertices and without a perfect matching or an almost perfect matching.The strong matching preclusion number of G,denoted by smp?G?,is the minimum number of vertices and edges whose deletion results in a graph with neither perfect matchings nor almost-perfect matchings.As a generalization,Liu and Liu recently introduced the concept of fractional matching preclusion number.The fractional matching preclusion number of G,denoted by f mp?G?,is the minimum number of edges whose deletion leaves the resulting graph without a fractional per-fect matching.The fractional strong matching preclusion number of G,denoted by fsmp?G?,is the minimum number of vertices and edges whose deletion leaves the resulting graph without a fractional perfect matching.In this paper,the matching preclusion of triangular mesh and butterfly derived networks are studied.The following results are obtained.1.The results of triangular mesh T_nare as follows:?1?The matching preclusion number and conditional matching preclusion num-ber of radix triangular mesh with odd vertices are mp?T_n?=4 and mp₁?T_n?=6,respectively;The conditional matching preclusion number of radix triangular mesh with even vertices is mp₁?T_n?=3;?2?When n?4,the strong matching preclusion number,fractional matching preclusion number and fractional strong matching preclusion number of radix triangu-lar mesh are smp?T_n?=2,f mp?T_n?=2 and fsmp?T_n?=2,respectively.2.The results for butterfly derived networks are as follows:?1?When r is odd,the fractional matching preclusion number and fractional strong matching preclusion number of butterfly network are f mp?BF?r??=2 and fsmp?BF?r??=1,respectively;When r is even,the fractional matching preclusion number and fractional strong matching preclusion number of butterfly network are f mp?BF?r??=0 and fsmp?BF?r??=0,respectively;?2?When n?3,the fractional matching preclusion number and fractional strong matching preclusion number of augmented butterfly network are f mp?ABF?n??=3and fsmp?ABF?n??=2,respectively;?3?When n?3,the fractional matching preclusion number and fractional strong matching preclusion number of enhanced butterfly network are f mp?EBF?r??=2and fsmp?EBF?r??=2,respectively.