PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Treść / Zawartość
Identyfikatory
Warianty tytułu
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).
Rocznik
Strony
375--382
Opis fizyczny
BIbliogr. 9 poz.
Twórcy
  • University of Tehran Department of Industrial Design College of Fine Arts Tehran, Iran
  • 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
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-f7995dff-9bec-4e9e-bc12-e4f9274a7453
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.