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.
- A. Bishnu, K. Dutta, A. Gosh, S. Pual, \([1,j]\)-set problem in graphs, Discrete Math. 339 (2016), 2215-2525.
- 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.
- M. Chellali, T.W. Haynes, S.T. Hedetniemi, A. McRae, \([1,2]\)-sets in graphs, Discrete Appl. Math. 161 (2013), 2885-2893.
- 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.
- 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.
- 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.
- R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, CRC Press, 2011.
- N. Ghareghani, I. Peterin, P. Sharifani, \([1,k]\)-domination number of lexicographic products of graphs, Manuscript (2019).
- 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.
- Received: 2019-10-06.
- Revised: 2020-02-25.
- Accepted: 2020-02-26.
- Published online: 2020-04-04.
