English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 PerfectMatchings in a Convex Geometric Graph], the smallest sets of edges that meetall the simple perfect matchings (SPMs) in $CGG(2m)$ (called "blockers") arecharacterized, and it is shown that all these sets are caterpillar graphs witha special structure, and that their total number is $m \cdot 2^{m-1}$. In thispaper we characterize the co-blockers for SPMs in $CGG(2m)$, that is, thesmallest sets of edges that meet all the blockers. We show that the co-blockersare exactly those perfect matchings $M$ in $CGG(2m)$ where all edges are of oddorder, 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 blockersgrow exponentially with $m$, the number of co-blockers growssuper-exponentially.

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