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

• Autorzy: Ghareghani Narges , Peterin Iztok , Sharifani Pouyeh

Identyfikatory

DOI

10.7494/OpMath.2020.40.3.375

• Języki publikacji: EN

Abstrakty

EN

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 fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).

Słowa kluczowe

EN

domination; [1, k]-domination number; [l,k]-total domination number; bipartite graphs

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2020
• Tom: Vol. 40, no. 3
• Strony: 375--382
• Opis fizyczny: BIbliogr. 9 poz.

Twórcy

autor

Ghareghani Narges

• University of Tehran Department of Industrial Design College of Fine Arts Tehran, Iran

autor

Peterin Iztok

• University of Maribor Faculty of Electrical Engineering and Computer Science Koroska 46, 2000 Maribor, Slovenia
• Institute of Mathematics, Physics, and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia

autor

Sharifani Pouyeh

• Institute for Research in Fundamental Sciences (IPM) School of Mathematics Tehran, Iran

Bibliografia

• [1] A. Bishnu, K. Dutta, A. Gosh, S. Pual, [l,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 [l,k]-sets in graphs, Australasian J. Combin. 59 (2014), 144-156.
• [3] M. Chellali, T.W. Haynes, S.T. Hedetniemi, A. McRae, [l,2]-sete 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, [l,2]-sete and [l,2]-totaZ sets in trees with algorithms, Discrete Appl. Math. 198 (2016), 136-146.
• [6] P. Golovach, J. Kratochvil, 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. Klavzar, 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, [l,2]-domination in graphs, Discrete Appl. Math. 175 (2014), 79-86.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).