Journal of Interconnection Networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. There are other related parameters and generalization including the strong matching preclusion number, the conditional matching preclusion number, the fractional matching preclusion number, and so on. In this survey, we give an introduction on the general topic of matching preclusion.

A multiprocessor system and interconnection network have a underlying topology, which is usually presented by a graph, where nodes represent processors and links represent communication links between processors. The (conditional) matching preclusion number of a graph is the minimum number of edges whose deletion leaves the resulting graph (with no isolated vertices) that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that (1) the connectivity (edge connectivity) of the leaf-sort graph CF_n is $\frac{3n-3}{2}\left(\frac{3n-3}{2}\right)$ for odd n and $\frac{3n-4}{2}\left(\frac{3n-4}{2}\right)$ for even n; (2) CF_n is super edge-connected; (3) the matching preclusion number of CF_n is $\frac{3n-3}{2}$ for odd n and $\frac{3n-4}{2}$ for even n; (4) the conditional matching preclusion number of CF_n is 3n – 5 for odd n and n ≥ 3, and 3n – 6 for even n and n ≥ 4.

As spanning subgraphs of hypercubes, exchanged hypercubes contain less edges but maintain lots of desired properties of hypercubes. This paper considers matching preclusion, a kind of measures of edge-fault tolerance, of exchanged hypercubes EH(s, t). We show that EH(s, t) is maximally matched, that is, for s ≥ t, mp(EH(s, t)) = t + 1 and EH(s, t) is super matched if and only if (s, t) ≠ (1, 1). Comparing with results of matching preclusion for hypercubes, we conclude that exchanged hypercubes maintain the matching preclusion property of hypercubes, except for EH(1, 1).

The matching preclusion number of a graph is the minimum number of edges whose deletion leaves the resulting graph that has neither perfect matchings nor almost perfect matchings. This concept was introduced as a measure of robustness in the event of edge failure in interconnection networks. The pyramid network is one of the important networks applied in parallel and distributed computer systems. Chen et al. in 2004 proposed a new hierarchy structure, called the enhanced pyramid network, by replacing each mesh in a pyramid network with a torus. An enhanced pyramid network of n layers is denoted by EPM(n). In this paper, we prove that the matching preclusion number of EPM(n) is 9 where n ≥ 4.

The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion number of restricted hypercube-like graphs, which extend some known results.

Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect matching. Matching preclusion number was introduced for measuring the robustness of a network when there is a link failure. In this paper, we focus on conditional matching preclusion for folded hypercube FQ_n, an important variant of hypercube. We show that conditional matching preclusion number of FQ_n is 2n and all optimal conditional matching preclusion sets are trivial for n ⩾ 5.