Higher-order triangular-distance Delaunay graphs: Graph-theoretical properties

We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set P of points in general position in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle ▽, and there is an edge between two points in P if and only if there is an empty homothet of ▽ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely k-TD, which contains an edge between two points if the interior of the smallest homothet of ▽ having the two points on its boundary contains at most k points of P. We consider the connectivity, Hamiltonicity and perfect-matching admissibility of k-TD. Finally we consider the problem of blocking the edges of k-TD.