Matching Preclusion Problem in Restricted HL-graphs and Recursive Circulant $G(2^m,4)$
Jung-Heum Park · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2008
The matching preclusion set of a graph is a set of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. The matching preclusion number is the minimum cardinality over all matching preclusion sets. We show in this paper that, for any , the matching preclusion numbers of both m-dimensional restricted HL-graph and recursive circulant are equal to degree m of the networks, and that every minimum matching preclusion set is the set of edges incident to a single vertex.