Conditional Matching Preclusion for Hypercube-Like Interconnection Networks

Free registration required

Executive Summary

The conditional matching preclusion number of a graph with n vertices is the minimum number of edges whose deletion results in a graph without an isolated vertex that does not have a perfect matching if n is even, or an almost perfect matching if n is odd. The authors develop some general properties on conditional matching preclusion and then analyze the conditional matching preclusion numbers for some HL-graphs, hypercube-like interconnection networks. Given a graph G, a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex. They say that a vertex is matched if it is incident to an edge in the matching. Otherwise, the vertex is unmatched.

  • Format: PDF
  • Size: 908 KB