Opuscula Math. 40, no. 3 (2020), 375-382
https://doi.org/10.7494/OpMath.2020.40.3.375

Opuscula Mathematica

# A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices

Narges Ghareghani
Iztok Peterin
Pouyeh Sharifani

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.

Mathematics Subject Classification: 05C69.

Full text (pdf)

1. A. Bishnu, K. Dutta, A. Gosh, S. Pual, $$[1,j]$$-set problem in graphs, Discrete Math. 339 (2016), 2215-2525.
2. M. Chellali, O. Favaron, T.W. Haynes, S.T. Hedetniemi, A. McRae, Independent $$[1,k]$$-sets in graphs, Australasian J. Combin. 59 (2014), 144-156.
3. M. Chellali, T.W. Haynes, S.T. Hedetniemi, A. McRae, $$[1,2]$$-sets in graphs, Discrete Appl. Math. 161 (2013), 2885-2893.
4. O. Etesami, N. Ghareghani, M. Habib, M. Hooshmandasl, R. Naserasr, P. Sharifani, When an optimal dominating set with given constraints exists, Theoret. Comput. Sci. 780 (2019), 54-65.
5. A.K. Goharshady, M.R. Hooshmandasl, M.A. Meybodi, $$[1,2]$$-sets and $$[1,2]$$-total sets in trees with algorithms, Discrete Appl. Math. 198 (2016), 136-146.
6. P. Golovach, J. Kratochvíl, Computational complexity of generalized domination: a complete dichotomy for chordal graphs, [in:] International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 2007, pp. 1-11.
7. R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, CRC Press, 2011.
8. N. Ghareghani, I. Peterin, P. Sharifani, $$[1,k]$$-domination number of lexicographic products of graphs, Manuscript (2019).
9. X. Yang, B. Wu, $$[1,2]$$-domination in graphs, Discrete Appl. Math. 175 (2014), 79-86.
• Narges Ghareghani
• University of Tehran, Department of Industrial Design, College of Fine Arts, Tehran, Iran
• Iztok Peterin (corresponding author)
• University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška 46, 2000 Maribor, Slovenia
• Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
• Pouyeh Sharifani
• Institute for Research in Fundamental Sciences (IPM), School of Mathematics, Tehran, Iran
• Communicated by Dalibor Fronček.
• Revised: 2020-02-25.
• Accepted: 2020-02-26.
• Published online: 2020-04-04.