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 the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle $$t$$, and there is an edge between two points in $$P$$ if and only if there is an empty homothet of $$t$$ 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 homothet of $$t$$ 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.