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

DOI10.1007/S00454-013-9509-XMaRDI QIDQ368759zbMATHOpenAlexFDO

Authors Chaya Keller, Micha A. Perles

Publication date 23 September 2013

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

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

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)

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.

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

Cites work

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

Cited in

(5)

• 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
• 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

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)