TY  - JOUR
ID  - Ghareghani2020
LB  - Ghareghani2020
AU  - Ghareghani, Narges
AU  - Peterin, Iztok
AU  - Sharifani, Pouyeh
TI  - A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices
ST  - A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2020
VL  - 40
IS  - 3
SP  - 375
EP  - 382
DO  - https://doi.org/10.7494/OpMath.2020.40.3.375
UR  - https://doi.org/10.7494/OpMath.2020.40.3.375
AB  - A subset \(D\) of the vertex set \(V\) of a graph \(G\) is called an \([1,k]\)-dominating set if every vertex from \(V-D\) is adjacent to at least one vertex and at most \(k\) vertices of \(D\). A \([1,k]\)-dominating set with the minimum number of vertices is called a \(\gamma_{[1,k]}\)-set and the number of its vertices is the \([1,k]\)-domination number \(\gamma_{[1,k]}(G)\) of \(G\). In this short note we show that the decision problem whether \(\gamma_{[1,k]}(G)=n\) is an \(NP\)-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph \(G\) of order \(n\) satisfying \(\gamma_{[1,k]}(G)=n\) is given for every integer \(n \geq (k+1)(2k+3)\).
KW  - domination
KW  - \([1,k]\)-domination number
KW  - \([1,k]\)-total domination number
KW  - bipartite graphs
SN  - 1232-9274
ER  -