Matchings in higher-order Gabriel graphs

Given a set P of n points in the plane, the order-k Gabriel graph on P  , denoted by k-GGk-GG, has an edge between two points p and q if and only if the closed disk with diameter pq contains at most k points of P, excluding p and q  . We study matching problems in k-GGk-GG graphs. We show that a Euclidean bottleneck matching of P   is contained in 10-GG10-GG, but 8-GG8-GG may not have any Euclidean bottleneck matching. In addition we show that 0-GG0-GG has a matching of size at least n−14 and this bound is tight. We also prove that 1-GG1-GG has a matching of size at least 2(n−1)5 and 2-GG2-GG has a perfect matching. Finally we consider the problem of blocking the edges of k-GGk-GG.