Characterization of co-blockers for simple perfect matchings in a convex geometric graph

preprint2010arXivOpen access

Abstract

Consider the complete convex geometric graph on 2m2m vertices, CGG(2m)CGG(2m), i.e., the set of all boundary edges and diagonals of a planar convex 2m2m-gon PP. In [C. Keller and M. Perles, On the Smallest Sets Blocking Simple Perfect Matchings in a Convex Geometric Graph], the smallest sets of edges that meet all the simple perfect matchings (SPMs) in CGG(2m)CGG(2m) (called "blockers") are characterized, and it is shown that all these sets are caterpillar graphs with a special structure, and that their total number is m⋅2m−1m \cdot 2^{m-1}. In this paper we characterize the co-blockers for SPMs in CGG(2m)CGG(2m), that is, the smallest sets of edges that meet all the blockers. We show that the co-blockers are exactly those perfect matchings MM in CGG(2m)CGG(2m) where all edges are of odd order, and two edges of MM that emanate from two adjacent vertices of PP never cross. In particular, while the number of SPMs and the number of blockers grow exponentially with mm, the number of co-blockers grows super-exponentially.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.