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

DOI10.1007/S00454-013-9509-XzbMATH Open1272.05159arXiv1011.5883OpenAlexW2100167998MaRDI QIDQ368759FDOQ368759

Authors: Chaya Keller, Micha A. Perles 

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: 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 $mcdot{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.

Full work available at URL: https://arxiv.org/abs/1011.5883

Recommendations

• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• Blockers and transversals

zbMATH Keywords

blockersconvex geometric graphssemi-perfect matchings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Trees with Hamiltonian square
• The number of caterpillars
• On the smallest sets blocking simple perfect matchings in a convex geometric graph

Cited In (5)

• On the smallest sets blocking simple perfect matchings in a convex geometric graph
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Flip graphs, Yoke graphs and diameter
• Blockers for simple Hamiltonian paths in convex geometric graphs of odd order
• Blockers for triangulations of a convex polygon and a geometric maker-breaker game

This page was built for publication: Characterization of co-blockers for simple perfect matchings in a convex geometric graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368759)