Opuscula Math. 40, no. 3 (2020), 375-382

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.
  • Received: 2019-10-06.
  • Revised: 2020-02-25.
  • Accepted: 2020-02-26.
  • Published online: 2020-04-04.
Opuscula Mathematica - cover

Cite this article as:
Narges Ghareghani, Iztok Peterin, Pouyeh Sharifani, A note on bipartite graphs whose [1,k]-domination number equal to their number of vertices, Opuscula Math. 40, no. 3 (2020), 375-382, https://doi.org/10.7494/OpMath.2020.40.3.375

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.