# On $d$-distance $m$-tuple ($\\ell, r$)-domination in graphs

Source: [On $d$-distance $m$-tuple ($\\ell, r$)-domination in graphs](<https://www.sota2.com/research/paper/68fa580a1e209131ce9aaace>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T15:05:34.824Z

Authors: Sangram K. Jena, Ramesh K. Jallu, Gautam K. Das

Published: 2019-07-26T08:01:10.000Z

## Abstract

In this article, we study the $d$-distance $m$-tuple ($\\ell, r$)-domination problem. Given a simple undirected graph $G=(V, E)$, and positive integers $d, m, \\ell$ and $r$, a subset $V' \\subseteq V$ is said to be a $d$-distance $m$-tuple ($\\ell, r$)-dominating set if it satisfies the following conditions: (i) each vertex $v \\in V$ is $d$-distance dominated by at least $m$ vertices in $V'$, and (ii) each $r$ size subset $U$ of $V$ is $d$-distance dominated by at least $\\ell$ vertices in $V'$. Here, a vertex $v$ is $d$-distance dominated by another vertex $u$ means the shortest path distance between $u$ and $v$ is at most $d$ in $G$. A set $U$ is $d$-distance dominated by a set of $\\ell$ vertices means size of the union of the $d$-distance neighborhood of all vertices of $U$ in $V'$ is at least $\\ell$. The objective of the $d$-distance $m$-tuple ($\\ell, r$)-domination problem is to find a minimum size subset $V' \\subseteq V$ satisfying the above two conditions.   We prove that the problem of deciding whether a graph $G$ has (i) a 1-distance $m$-tuple ($\\ell, r$)-dominating set for each fixed value of $m, \\ell$, and $r$, and (ii) a $d$-distance $m$-tuple ($\\ell, 2$)-dominating set for each fixed value of $d (\> 1), m$, and $\\ell$ of cardinality at most $k$ (here $k$ is a positive integer) are NP-complete. We also prove that for any $\\varepsilon\>0$, the 1-distance $m$-tuple $(\\ell, r)$-domination problem and the $d$-distance $m$-tuple $(\\ell,2)$-domination problem cannot be approximated within a factor of $(\\frac{1}{2}- \\varepsilon)\\ln \|V\|$ and $(\\frac{1}{4}- \\varepsilon)\\ln \|V\|$, respectively, unless $P = NP$.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1907.11416>)

[PDF](<https://arxiv.org/pdf/1907.11416.pdf>)