Mathematics – Combinatorics
Scientific paper
2010-11-25
Mathematics
Combinatorics
8 pages, 4 figures
Scientific paper
Consider the complete convex geometric graph on $2m$ vertices, $CGG(2m)$, i.e., the set of all boundary edges and diagonals of a planar convex $2m$-gon $P$. 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)$ (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 \cdot 2^{m-1}$. In this paper we characterize the co-blockers for SPMs in $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 $M$ in $CGG(2m)$ where all edges are of odd order, and two edges of $M$ that emanate from two adjacent vertices of $P$ never cross. In particular, while the number of SPMs and the number of blockers grow exponentially with $m$, the number of co-blockers grows super-exponentially.
Keller Chaya
Perles Micha A.
No associations
LandOfFree
Characterization of co-blockers for simple perfect matchings in a convex geometric graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Characterization of co-blockers for simple perfect matchings in a convex geometric graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Characterization of co-blockers for simple perfect matchings in a convex geometric graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-463636