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.