Download Now Free registration required
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