Efficient k k -limited Dominating Broadcasts in Product Graphs Bharadwaj, A.Senthil Thilak Abstract In a graph G G , a subset of vertices S S is called an efficient dominating set (EDS) if every vertex in the graph is uniquely dominated by exactly one vertex in S S . A graph is said to be efficiently dominatable if it contains an EDS. Additionally, a function f : V ⁡ ( G ) → { 0 , 1 , 2 , … , k } f:V(G)\rightarrow\{0,1,2,\dots,k\} is termed a k k -limited dominating broadcast if, for every vertex u ∈ V ⁡ ( G ) u\in V(G) , there exists a vertex v v , with f ⁡ ( v ) ≥ 1 f(v)\geq 1 such that d ⁡ ( u , v ) ≤ f ⁡ ( v ) d(u,v)\leq f(v) . A vertex u u is said to be dominated by a vertex v v . In this work, we unify these two concepts to explore the notion of efficient k k -limited broadcast domination in graphs. A k k -limited dominating broadcast f f is called an efficient k k -limited dominating broadcast ( k k - E ​ L ​ D ​ B ELDB ) if each vertex in the graph is dominated exactly once. The minimum value of k k for which the given graph G G has k k - E ​ L ​ D ​ B ELDB is defined as m ​ c ​ r ​ ( G ) mcr(G) . We prove determining m ​ c ​ r ​ ( G ) mcr(G) is NP-Complete for general graphs and explore the m ​ c ​ r ​ ( G ) mcr(G) values and other related parameters on standard graphs and their products. Mathematics Subject Classification]05C69, 05B40. keywords Efficient k-limited broadcast domination pacs [ 1 Introduction ————————————————— Given a graph G=(V,E) , a set S\subseteq V(G) is called a dominating set if each vertex v\in V(G) is either in S or has at least one neighbor in S . The size of the smallest dominating set of G is referred to as the domination number of G and is denoted by \gamma(G) . The open neighborhood of a vertex v , denoted by N(v) , is the set of all vertices adjacent to v . The closed neighborhood of v , denoted by N[v] , is defined as N(v)\cup\{v\} . A set S\subseteq V(G) is an efficient dominating set ( EDS ) of G if |N[v]\cap S|=1 for all v\in V(G) . In other words, S is an EDS if each vertex v\in V(G) is dominated by exactly one vertex (including itself) in S . Not every graph possesses an EDS . If a graph G has an EDS , then it is said to be efficiently dominatable . The distance between a pair of vertices u and v is the length of the shortest path between u and v , denoted by d(u,v) . A set S\subseteq V(G) is a 2-packing if for each pair u,v\in S , N[u]\cap N[v]=\emptyset . If S is a 2-packing , then d(u,v)\geq 3, for all u,v\in S . Thus, a dominating set is an EDS if and only if it is a 2 -packing. The influence of a set S\subseteq V(G) is denoted by I(S) and is the number of vertices dominated by S (inclusive of vertices in S ). If S is a 2 -packing, then I(S)=\sum_{v\in S}[1+\deg(v)]. The maximum influence of a 2 -packing of G is called the efficient domination number of G and is denoted by F(G) . That is, F(G)=\max\{I(S):~S\text{ is a 2-packing}\}=\max\left\{\sum_{v\in S}(1+\operatorname{deg}v):S\subseteq V(G)\right. and \left.|N[x]\cap S|\leq 1,\forall~x\in V(G)\right\} . Clearly, 0\leq F(G)\leq|V(G)| and G is efficiently dominatable if and only if F(G)=|V(G)| . A 2 -packing with influence F(G) is called an F(G) -set . The concept of efficient domination is found in the literature under different names such as perfect codes or perfect 1 -codes Biggs (1973) , independent perfect domination Chain-Chin and Lee (1996) , perfect 1 -domination Livingston and Stout (1990) , and efficient domination Bange (1988) . In this paper, we use the terminology efficient domination introduced by Bange et al. Bange (1988) . The problem of determining whether F(G)=|V(G)| is \mathcal{NP} -complete on arbitrary graphs Bange (1988) as well as on some special/restricted classes of graphs such as bipartite graphs, chordal graphs, planar graphs of degree at most three, etc. Haynes et al. (2013) . In contrast, it is solvable in polynomial time for trees Bange (1988) . Goddard et al. Goddard et al. (2000) have derived bounds on the efficient domination number of arbitrary graphs and trees. Efficient domination has also been studied in various special classes of graphs such as chordal bipartite graphs Lu and Tang (2002) , the strong product of arbitrary graphs Abay-Asmerom et al. (2009) , and the Cartesian product of cycles Chelvam and Mutharasu (1943) . Hereditary efficiently dominatable graphs were defined and studied in Milanič (2013) and Barbosa and Slater (2016) . The concept of perfect codes or efficient domination finds wide applications in coding theory, resource allocation in computer networks, and more Vaishampayan et al. (2001) ; Livingston and Stout (1988) . In 2001, Erwin introduced a variant of domination termed broadcast domination , which models multiple broadcast stations with associated transmission powers capable of disseminating messages to locations beyond a unit distance. A broadcast on a graph G is a function f:V(G)\rightarrow\{0,1,2,\dots,\text{diam}(G)\} with f(v)\leq\text{ecc}(v) for all v\in V(G) . A vertex v is a broadcasting vertex if f(v)\geq 1 , and the set of all broadcasting vertices is denoted by V_{f}^{+}(G) or simply V_{f}^{+} . The set of vertices with f(v)=0 is denoted by V_{f}^{0}(G) . A vertex u\in V(G) is said to be f-dominated if there is a vertex v\in V_{f}^{+} such that d(v,u)\leq f(v) . Then, vertex u is said to hear the broadcast from vertex v . The set of vertices that vertex u can hear is defined as H(u)=\{v\in V_{f}^{+}\mid d(u,v)\leq f(v)\} . A vertex u is overdominated if there is a broadcasting vertex v corresponding to a broadcast f such that d(u,v)k . Thus, the study of the minimum value of k for which a graph is k -efficiently dominatable is significant, and we call it the minimum covering radius of a graph, denoted by \text{mcr}(G) . Definition 1.2 . The minimum covering radius of a graph is the minimum value of k for which the graph is k -efficiently dominatable. It can be noted that for any graph G , 1\leq\text{mcr}(G)\leq\operatorname{rad}(G) . We define the optimal cost of k - ELDB as follows: Definition 1.3 . The k -efficient broadcast domination number of a graph G , denoted by \gamma_{ebk}(G) , is defined as: \gamma_{ebk}(G)=\min\left\{\sum_{v\in V_{f}^{+}}f(v)\mid f\text{ is a $k$-ELDB on $G$}\right\}. Observation 1.1 . \gamma_{eb1}(G)\leq\gamma_{eb2}(G)\leq\dots\leq\gamma_{ebk}(G) , where k=\text{mcr}(G) . If k -ELDB does not exist on the graph G for any k<\text{mcr}(G) , we find the maximum number of vertices that a k -ELDB can dominate. Definition 1.4 . The k -efficient covering number, denoted by F_{k}(G) , is defined as: F_{k}(G)=\max\left\{\left|\bigcup_{v\in V_{f}^{+}}N_{f}[v]\right|\mid f\text{ is a $k$-ELDB on $G$}\right\}. Observation 1.2 . F(G)\leq F_{2}(G)\leq\dots\leq F_{\operatorname{rad}(G)}=|V(G)| The concept of an efficient k -limited dominating broadcast is particularly useful in applications where redundancy minimization and precise control are necessary. In the design of urban surveillance systems, for example, efficient broadcast can help position cameras such that each area is monitored by exactly one camera, optimizing resource allocation. In distributed computing, an efficient broadcast can be used to identify optimal node placements to achieve efficient and fault-tolerant communication protocols. 2 Efficient k -limited dominating broadcast on different classes of graphs This section aims to investigate k - ELDB on specific graph classes: Paths ( P_{n} ), Cycles ( C_{n} ), Subdivision of stars ( S_{i}(K_{1,n} )), Complete graphs ( K_{m} ), lexicographic, strong and cartesian product of graphs. It can be noted that if mcr(G)=1 , then G is efficiently dominatable. 2.1 Results on some well-known graphs Theorem 2.1 . \frac{2n}{1+\Delta^{2}}\leq\gamma_{eb2}(G)\leq\frac{n}{1+\delta(G)} Proof. A vertex receiving cost 2 can dominate at most 1+\Delta+\Delta(\Delta-1)=1+\Delta^{2} number of vertices. On the other hand, a broadcasting vertex receiving cost 1 dominates at least {1+\delta(G)} number of vertices. ∎ Theorem 2.2 . P_{n} is 1 -efficiently dominatable. \gamma_{eb1}(P_{n})=\gamma_{ebk}(P_{n})=\left\lceil\frac{n}{3}\right\rceil,\forall k\geq 2 . Theorem 2.3 . mcr(C_{n})=\begin{cases}{1}&\mbox{if $n\equiv 0$ $(mod3)$ }\\ {2}&\mbox{if $n\equiv 1$ or $2$ $(mod3)$, $n\neq 7$}\\ {3}&\mbox{if $n=7$}\end{cases} \gamma_{ebk}(C_{n})=\left\lceil\frac{n}{3}\right\rceil , where k=mcr(C_{n}) . Proof. A vertex assigned a cost of 1 and 2 dominates three and five vertices (including itself), respectively. It is evident that in any \gamma_{ebk} -broadcast of C_{n} , minimizing the number of vertices assigned a cost of 2 is essential to reduce the total cost. Case(i): n\equiv 0\pmod{3} That is, n=3k , a vertex with a cost of 1 can dominate three vertices. Hence, k vertices, each assigned a cost of 1 and positioned at a distance of 3 , constitute a 1 - ELDB of C_{n} . Case(ii): n\equiv 1\pmod{3} That is, n=3k+1 , we focus on n\geq 10 as the result holds for n=4 . Since n=2(5)+(k-3)(3) , k-3 vertices are assigned a cost of 1 , and two vertices are assigned a cost of 2 . Thus, k+1 vertices form the set {V_{f}}^{+} for the \gamma_{ebk} -broadcast. Case(iii): n\equiv 2\pmod{3} That is, n=3k+2 , then n=1(5)+(k-1)(3) implies that k-1 vertices are assigned a cost of 1 , and one vertex is assigned a cost of 2 . Therefore, k+1 vertices form the set {V_{f}}^{+} for the \gamma_{ebk} -broadcast. ∎ An edge subdivision is the insertion of a new vertex v_{j} in the middle of an existing edge e=v_{i}v_{k} accompanied by the joining of the original edge endpoints with the new vertex to form new edges e_{1}=v_{i}v_{j} and e_{2}=v_{j}v_{k} . Let (S_{i}(K_{1,n-1})) be i^{th} subdivision of a star graph. Let v_{0},v_{1},v_{2},\dots v_{i},v_{i+1} be the vertices on path from central vertex v_{0} to a leaf vertex v_{i+1} . There are n-1 such paths. Theorem 2.4 . mcr(S_{i}(K_{1,n-1}))=1 and \gamma_{eb1}(S_{i}(K_{1,n-1}))=\begin{cases}{\left\lceil\frac{i}{3}\right\rceil}(n-1)&\mbox{ if $i\equiv 1$ $(mod3)$}\\ {\left\lceil\frac{i}{3}\right\rceil}(n-1)+1&\mbox{ otherwise }\par\par\end{cases} Proof. We give 1 - ELDB and prove it is optimal. Let v_{0} be the central vertex of S_{i}(K_{1,n-1}) . P_{v_{o}v_{i+1}} denote the path from v_{0},v_{1},v_{2},\dots v_{i},v_{i+1} . Case(i): i\equiv 1\pmod{3} That is, i=3k+1 for k\geq 0 , Choose vertices v_{2},v_{5},\dots v_{i+1} of all such paths except one. Choose v_{1},v_{4},\dots v_{i} for that remaining path. Since to dominate each of these paths, we need at least a cost k+1 , and to dominate the whole graph, we need at least k(n-1) vertices. Case(ii): i\equiv 0 or 2\pmod{3} That is, i=3k or 3k+2 . Choose the central vertex v_{0} and vertices v_{3},v_{6},\dots v_{i+1} of all the paths. If v_{1} of any of these paths belong to {V_{f}}^{+} , then at least k+1 vertices need to dominate each of the other paths. Therefore v_{1}\notin{V_{f}}^{+} . By a similar argument as in case(i), at least k vertices are required to dominate each path P(v_{1},v_{3k+1}) . And since v_{1}\notin{V_{f}}^{+} , theorem holds. ∎ 2.2 Results on Product graphs 2.2.1 Lexicographic Product of graphs Definition 2.1 . Imrich et al. (2000) The lexicographic product of two graphs G and H is denoted by G\cdot H , whose vertex set is V(G)\times V(H) , in which two vertices (u,v) and (u^{\prime},v^{\prime}) are adjacent if 1. uu^{\prime}\in E(G) , or 2. u=u^{\prime} and vv^{\prime}\in E(H) . Throughout this section, we assume V(G)=\{u_{1},u_{2},\dots u_{m}\} and V(H)=\{v_{1},v_{2},\dots v_{n}\} be vertices of H , unless specified otherwise. The graphs G and H are called the factors of G\cdot H . For v\in V(H) , the induced subgraph G^{(v)} of G\cdot H , defined as G^{(v)}=<\{(u,v)\in V(G\cdot H):u\in V(G)\}> is called the G -layer with respect to v in G\cdot H . Analogously, for u\in V(G) , the induced subgraph H^{(u)} of G\cdot H , defined as H^{(u)}=<\{(u,v)\in V(G\cdot H):v\in V(H)\}> is called the H -layer with respect to u in G\cdot H . Since d((u_{i},v_{j}),(u_{i},x))\leq 2 , we have the following observation. Observation 2.1 . \forall u_{i}\in V(G) , there exists at most one broadcasting vertex v in V(H^{u_{i}}) . Proposition 2.5 . Let f be k - ELDB of G\cdot H such that f(u_{i},v_{j})=1 , then \operatorname{rad}(H)=1 with central vertex v_{j} . Proof. Assume the contrary. Let v_{j},v_{k}\in V(H) such that v_{j}v_{k}\notin E(H) . By observation 2.1 , (u_{i},v_{k}) has to be dominated by some vertex of H^{(u_{p})} , where u_{p}\in N(u_{i}) . It can be noted that all vertices of H^{u_{p}} , where u_{p}\in N(u_{i}) are dominated by (u_{i},v_{j}) and hence (u_{i},v_{k}) is left undominated by f contradiction to f being dominating broadcast. ∎ Theorem 2.6 . mcr(G\cdot H)\geq mcr(G) Proof. Let mcr(G)=k . Assume, for contradiction, that mcr(G\cdot H)=pp . ∎ Next, we explore by fixing G as P_{m} and C_{m} in G\cdot H . Theorem 2.7 . mcr(P_{m}\cdot H)=1 if and only if \operatorname{rad}(H)=1 . Theorem 2.8 . If m\geq 2 and \operatorname{rad}(H)\neq 1 , mcr(P_{m}\cdot H)=2 and \gamma_{eb2}(P_{m}\cdot H)=2\left\lceil\frac{m}{5}\right\rceil Proof. Let V(G)=\{u_{1},u_{2},\dots u_{m}\} and V(H)=\{v_{1},v_{2},\dots v_{n}\} . We obtain 2 - ELDB for P_{m}\cdot H as follows. By Proposition 2.5 , no vertex receives the cost 1 . If a vertex (u_{i},v_{j}) receives cost 2 , it dominates all the vertices of H^{(u_{k})} , where k\in\{i-2,i-1,i,i+1,i+2\} and it dominates no other vertices. So, the problem reduces to dominating the vertices of P_{m} using cost 2 . Since this can be done for any value of m and P_{m} can be efficiently dominated with the total cost of 2\left\lceil\frac{m}{5}\right\rceil , the theorem holds. ∎ Corollary 2.1 . If m\geq 2 , mcr(P_{m}\cdot H)=\begin{cases}{1}&\mbox{if $\operatorname{rad}(H)=1$ }\\ {2}&\mbox{otherwise}\\ \end{cases} It can be noted that if f is a k - ELDB of a graph G such that f(u)\neq 1,\forall u\in V(G) , then f restricted to G^{(v_{1})} is a k - ELDB of G\cdot H . We call a graph G , a 1 -free if it possesses a k - ELDB f , such that f(u)\neq 1,\forall u\in V(G) . For example, P_{n} are 1 -free graphs as any P_{n} can be efficiently dominated with cost 2 alone. We call P_{n} is [2]-\{1\} efficiently dominatable. Every graph G is [\operatorname{rad}]-\{1,2,\dots,\operatorname{rad}-1\} efficiently dominatable. Theorem 2.9 . If a graph G is [k]-\{1\} -efficiently dominatable, then G\cdot H is [k]-\{1\} -efficiently dominatable Corollary 2.2 . If k is the minimum value for which a 1 -free graph G is [k]-\{1\} efficiently dominatable, then mcr(G\cdot H)=k . Corollary 2.3 . If a graph G is 1 -efficiently dominatable, then mcr(G\cdot H)\geq 2 if and only if \operatorname{rad}(H)\neq 1 Theorem 2.10 . mcr(C_{m}\cdot H)=1 if and only if m\equiv 0(mod3) and \operatorname{rad}(H)=1 . And in all other cases, mcr(C_{m}\cdot H)=\begin{cases}{2}&\mbox{if $m\equiv 0(mod5)$ and $m\in\{3,4\}$ }\\ {4}&\mbox{if $m\in\{9,16,18,23$\lx@text@rbrace}\\ {5}&\mbox{if $m=11$}\\ {6}&\mbox{if $m=13$}\\ {3}&\mbox{otherwise}\\ \end{cases} Proof. Since no vertex receives cost 1 , and vertices receiving cost 2,3,4,5,6 dominates 5,7,9,11,13 number of vertices on C_{m} , the problem can be viewed as a number theory question: write m as repeated summation of 5,7,9,11,13 such that use smaller numbers as much as possible. Hence, the theorem holds. ∎ 2.2.2 Strong Product of graphs Definition 2.2 . Imrich et al. (2000) A Strong product of two graphs G and H is denoted by G\boxtimes H , whose vertex set is V(G)\times V(H) , in which two vertices (u,v) and (u^{\prime},v^{\prime}) are adjacent if (i) u=u^{\prime} and vv^{\prime}\in E(H) , or v=v^{\prime} and uu^{\prime}\in E(G) (ii) uu^{\prime}\in E(G) and vv^{\prime}\in E(H) . Throughout this section, we use u_{i}^{\prime}s and v_{j}^{\prime}s for vertices of G and H , respectively. G^{(v_{j})} and H^{(u_{i})} are defined analogously to that defined in the above section of the lexicographic product of graphs. Theorem 2.11 . Imrich et al. (2000) The distance betweeen two vertices (u,v) and (u^{\prime},v^{\prime}) in the graph G\boxtimes H is max\{d(u,u^{\prime}),d(v,v^{\prime})\} . Corollary 2.4 . If f(u_{i},v_{j})=d and if d_{H}(v_{l},v_{j})\leq d , then (u_{i},v_{j}) dominates vertex (u_{p},v_{j}) if and only if it dominates the vertex (u_{p},v_{l}) . Theorem 2.12 . mcr(G\boxtimes H)\geq max\{mcr(G),mcr(H)\} Proof. Without loss of generality, assume mcr(G)\geq mcr(H) . Let mcr(G)=k . Assume the contrary, that is mcr(G\boxtimes H)=ll . ∎ Theorem 2.13 . Abay-Asmerom et al. (2009) If G and H are efficiently dominatable, then G\boxtimes H is efficiently dominatable. That is, in theorem 2.13 , it was proved that if mcr(G)=1 and mcr(H)=1 , then mcr(G\boxtimes H)=1 . That is the equality of theorem 2.12 holds in this case. Next, we consider C_{m}\boxtimes P_{n} . Theorem 2.14 . mcr(C_{m}\boxtimes P_{n})=mcr(C_{m}) Proof. Let mcr(C_{m})=k . We prove this by constructing an efficient k -limited dominating broadcast of C_{m}\boxtimes P_{n} . Note that P_{n} admits a perfect d -code for all d\leq\operatorname{rad}(P_{n}) . Case(i): m\equiv 0\pmod{3} The theorem follows directly from Theorems 2.3 and 2.13 . Case(ii): m=4 Assign a perfect 2 -code of P_{n} to one of the P_{n} factors. By Corollary 2.4 , every vertex in C_{4}\boxtimes P_{n} is dominated. Thus, mcr(C_{4}\boxtimes P_{n})\leq 2 . Case(iii): m=7 Assign a perfect 3 -code of P_{n} to one of the P_{n} factors. Again, by Corollary 2.4 , every vertex in C_{7}\boxtimes P_{n} is dominated. Hence, mcr(C_{7}\boxtimes P_{n})\leq 3 . Case(iv): For m values other than those mentioned above Assign a perfect 2 -code of P_{n} to one of the P_{n} factors, say P_{n}^{(v_{3})} . This assignment dominates all vertices in C_{m}^{(v_{j})} for 1\leq j\leq 5 . The induced subgraph H of undominated vertices forms P_{m-5}\boxtimes P_{n} . Assign weights of 2 and 1 to the vertices of H such that each vertex with weight 2 dominates 5 vertices, and each vertex with weight 1 dominates 3 vertices, within their respective P_{m-5} factors of H . Consequently, mcr(C_{m}\boxtimes P_{n})\leq mcr(C_{m}) . By Theorem 2.12 , it follows that mcr(C_{m}\boxtimes P_{n})=mcr(C_{m}) . ∎ Corollary 2.5 . The broadcast defined in the proof of theorem 2.14 is \gamma_{ebk}- broadcast of C_{m}\boxtimes P_{n} Corollary 2.6 . If a graph H has perfect 1 -code and a perfect 2 -code, then mcr(C_{m}\boxtimes H)=mcr(C_{m}) . Theorem 2.15 . If \operatorname{rad}(G)=1 , then mcr(G\boxtimes H)=mcr(H) , \gamma_{ebk}(G\boxtimes H)=\gamma_{ebk}(H) , where k=mcr(H) Proof. Consider the k - ELDB of H with respect to the factor H^{(u_{i})} , where u_{i} represents the central vertex of G . If a broadcasting vertex v_{j} in H dominates a vertex v_{p} in H , then the vertex (u_{i},v_{j}) , inheriting the same cost as v_{j} , dominates all vertices in G^{(v_{p})} . Hence, the theorem holds. ∎ Corollary 2.7 . mcr(K_{1,n}\boxtimes H)=mcr(K_{m}\boxtimes H)=mcr(H) , \gamma_{ebk}(K_{1,n}\boxtimes H)=\gamma_{ebk}(K_{m}\boxtimes H)=\gamma_{ebk}(H) , where k=mcr(H) . Thus far, given a graph G , we have determined mcr(G) . In the next section, we address the converse problem. 3 Computational hardness of efficient k -limited broadcast domination problem Given any integer k , does there exist a graph G such that mcr(G)=k ? We answer the question of the existence of such graphs by construction. 3.1 Construction of a class of trees T_{k} A vertex adjacent to a leaf vertex is said to be a support vertex. Observation 3.1 . If f is an efficient dominating broadcast on a graph G , then there exists no support vertex at a distance f(v) from a broadcasting vertex v . For k\geq 2 , we give a recursive construction for a family of trees T_{k} with mcr(T_{k})=k . That is, there exists no efficient (k-1) -limited dominating broadcast on T_{k} . Construction 1 . Assigning step: Let T_{1}=K_{2} Iterative step: Hook two copies of P_{3} , each at the diametrical endpoints of the graph T_{i-1} to get T_{i} Recursive step: Repeat Step 2 until i=k Figure 1: Graphs of T_{k} We observe that T_{k} is a bicentral tree. Lemma 3.1 . Graph T_{k} admits an unique efficient k -limited dominating broadcast, where one of the central vertex receives the cost k . i.e., mcr(T_{k})=k . Proof. Let f be the assignment such that f(u)=k for u being one of the central vertices of the graph. Suppose there exists another assignment g that differs from f . According to Observation 3.1 , the leaf vertices excluding the diametrical endpoints of T_{k} has to be assigned a cost of 1. This assignment ensures dominating all vertices, except for the two end copies of P_{3} . Since eccentricity ecc(v)\geq k+1 for all vertices v other than the central vertices, the assignment f is the unique efficient k -limited dominating broadcast up to isomorphism. ∎ 3.2 NP-Completeness of efficient k -limited broadcast domination The decision version of k - ELDB problem is stated as follows Instance: A graph G and an integer k . Decision Problem: Determine whether G admits an efficient k - limited broadcast domination. To prove that the k - ELDB problem is NP-commplete, we establish its reduction from Exact 3-SAT problem as below. The EXACT 3-SAT problem: Instance: A CNF formula with m clauses C_{1},C_{2},\dots,C_{m} and n literals u_{1},u_{2},\dots,u_{n} . Decision Problem: Determine whether there exists a truth assignment function T:u_{i}\rightarrow\{0,1\} such that the CNF formula is satisfied with exactly one of the three literals in each clause being assigned the value true(1). In the next theorem, we give a reduction from EXACT 3-SAT to k -efficient broadcast domination problem. Theorem 3.1 . Efficient k -limited broadcast domination problem is NP-complete. Proof. We present a reduction from the EXACT 3-SAT problem. Given an instance of the Exact 3-SAT problem, which consists of CNF formula with m clauses, C_{1},C_{2},...C_{m} and n literals, U=\{u_{1},u_{2},...,u_{n}\} . We construct a graph of (3k-2)m+(4k-2)n number of vertices and certain number of edges as shown in the construction. For each u_{i} , draw a copy of T_{k} , and name the central vertices as u_{i} and \overline{u_{i}} . Draw m vertices C_{1},C_{2},\dots C_{m} . If C_{i}=u_{j}\vee\overline{u_{k}}\vee u_{l} , then draw three edges incident from C_{i} to u_{j},\overline{u_{k}} and u_{l} . Subdivide each of these edge k-1 times, which lead to a path from C_{i} to u_{j} , C_{i} to \overline{u_{k}} , C_{i} to u_{l} . We call them as Q_{ij},Q_{i\overline{k}},Q_{il} respectively. Let P_{ij}=Q_{ij}-\{u_{j}\} , P_{i\overline{k}}=Q_{i\overline{k}}-\{\overline{u_{k}}\} . Figure 2: Reduction graph G_{1} for an example of CNF, where C_{1}=\{u_{1},u_{2},u_{3}\},C_{2}=\{u_{1},\overline{u_{2}},\overline{u_{5}}\} , etc… Claim 1: If there exists a truth assignment T:u_{i}\rightarrow\{0,1\} satisfying CNF for the EXACT 3-SAT problem, then there exists an efficient k -limited dominating broadcast f on a graph G_{1} . Proof of claim 1: If T(u_{i})=1 , then assign f(u_{i})=k . If T(u_{i})=0 , then assign f(\overline{u_{i}})=k . Set f(v)=0 for the remaining vertices of G_{1} . Each vertex in T_{k} is dominated by the corresponding central vertex ( u_{i} or \overline{u_{i}} ) that has been assigned the cost k . Since only one literal is true for each clause C_{j} , the vertex corresponding to that literal dominates C_{j} , and d(C_{j},u_{i})>k for all other broadcasting vertices. The vertices of degree two are at most a distance k from the corresponding u_{i} or \overline{u_{i}} , and at least a distance k+1 from other broadcasting vertices, ensuring they are dominated exactly once. Therefore, f is an efficient k -limited dominating broadcast. If we prove the f obtained in claim 1 is the only efficient k -limited dominating broadcast on G_{1} , then the other way is also true. In claim 2, we provide a proof of this assertion. Claim 2: If there exists an efficient k -limited dominating broadcast on G_{1} , then there exists a truth assignment T:u_{i}\rightarrow\{0,1\} that satisfies CNF. Proof of claim 2: Based on Observations 3.1 and Lemma 3.1 , in any efficient k -limited dominating broadcast function f , the vertices in T_{k} must be dominated by either the corresponding u_{i} or \overline{u_{i}} , and no vertex in P_{ij} can dominate vertices in T_{k} . Consequently, we have f(u_{i})=k or f(\overline{u_{i}})=k . It is important to note that all vertices in P_{ij} , except for C_{i} , are dominated. Since these vertices are at most a distance k from u_{j} and \overline{u_{j}} , one of u_{j} or \overline{u_{j}} must receive the cost k . Without loss of generality, let C_{i}=u_{j}\vee\overline{u_{k}}\vee u_{l} . All three literals are at a distance k from C_{i} . Therefore, exactly one of them (without loss of generality, u_{j} ) will receive the cost k , while the other two ( \overline{u_{k}} and u_{l} ) will not. However, for each u_{p} , where 1\leq p\leq n , either u_{p} or \overline{u_{p}} must receive the cost k . Consequently, \overline{u_{l}} and u_{k} will receive the cost k . Thus, for every clause C_{i} , all three literals within that clause are at a distance k from C_{i} . To dominate C_{i} exactly once, exactly one of these three literals receives the cost k , implying that the negated literals of the other two receives the cost k . Therefore, the broadcasting vertices are either u_{i} or \overline{u_{i}} . Let this assignment be denoted as f . We then construct the corresponding truth assignment T . If f(u_{i})=k , then T(u_{i})=1 . If f(\overline{u_{i}})=k , then T(u_{i})=0 . Suppose f provides an efficient k -limited dominating broadcast. In that case, every clause vertex C_{i} is dominated exactly once, implying that one of its three literals is true. Hence, T is a satisfying assignment for the EXACT 3-SAT problem. ∎ We proved that for general graphs, determining whether mcr(G)=k is NP-Complete. 4 Conclusion and future work The open problem posed in the broadcast domination chapter of Structures of Domination in graphs ( Haynes et al. (2021) )—determining the minimum value of k for which a graph admits an efficient k -limited dominating broadcast—serves as the primary motivation for this research. In this work, we constructed examples of graphs that are not k -efficiently dominatable and established that determining whether a general graph is k -efficiently dominatable is NP-complete. Furthermore, we investigated this concept on standard graphs, lexicographic products, and strong products of graphs by computing \text{mcr}(G) and \gamma_{ebk}(G) , alongside deriving other results. As a direction for future research, we are currently exploring efficient k -limited dominating broadcasts on trees and other classes of graphs.