@Article{Ghareghani2020,
author = "Ghareghani, Narges and Peterin, Iztok and Sharifani, Pouyeh",
title = "A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices",
journal = "Opuscula Math.",
year = "2020",
volume = "40",
number = "3",
pages = "375--382",
doi = "https://doi.org/10.7494/OpMath.2020.40.3.375",
url = "https://doi.org/10.7494/OpMath.2020.40.3.375",
abstract = "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)\).",
keywords = "domination, \([1,k]\)-domination number, \([1,k]\)-total domination number, bipartite graphs",
issn = "1232-9274"
}