Opuscula Math. 46, no. 2 (2026), 139-152
https://doi.org/10.7494/OpMath.202601201

 
Opuscula Mathematica

On the existence of independent \((1,k)\)-dominating sets for \(k\in\{1,2\}\) in two products of graphs

Paweł Bednarz
Adrian Michalski
Natalia Paja

Abstract. A subset \(J\) of vertices is said to be a \((1,k)\)-dominating set if every vertex \(v\) not belonging to the set \(J\) has a neighbour in \(J\) and there exists also another vertex in \(J\) within the distance at most \(k\) from \(v\). In this paper, we study the problem of the existence of independent \((1,k)\)-dominating sets for \(k\in\{1,2\}\) in the tensor product and in the strong product of two graphs. We give complete characterisations of these graph products, which have independent \((1,1)\)-dominating sets or independent \((1,2)\)-dominating sets, with respect to the properties of their factors.

Keywords: dominating set, independent set, multiple domination, secondary domination, tensor product, strong product.

Mathematics Subject Classification: 05C69, 05C76.

Full text (pdf)

  1. Y. Bai, S. Fujita, S. Zhang, Kernels by properly colored paths in arc-colored digraphs, Discrete Math. 341 (2018), 1523-1533. https://doi.org/10.1016/j.disc.2018.02.014
  2. D.W. Bange, A.E. Barkauskas, P.J. Slater, Efficient dominating sets in graphs, Appl. Discrete Math. 189 (1988), 189-199.
  3. P. Bednarz, On \((2-d)\)-kernels in the tensor product of graphs, Symmetry 13 (2021), 230. https://doi.org/10.3390/sym13020230
  4. P. Bednarz, C. Hernández-Cruz, I. Włoch, On the existence and the number of \((2-d)\)-kernels in graphs, Ars Combin. 121 (2015), 341-351.
  5. P. Bednarz, N. Paja, On \((2-d)\)-kernels in two generalizations of the Petersen graph, Symmetry 13 (2021), 1948.
  6. P. Bednarz, I. Włoch, An algorithm determining \((2-d)\)-kernels in trees, Util. Math. 102 (2017), 215-222.
  7. P. Bednarz, I. Włoch, On \((2-d)\)-kernels in the Cartesian product of graphs, Ann. Univ. Mariae Curie-Skłodowska Sect. A 70 (2016), 1-8. https://doi.org/10.17951/a.2016.70.2.1
  8. U. Bednarz, I. Włoch, Fibonacci numbers in graphs with strong \((1,1,2)\)-kernels, Bol. Soc. Mat. Mex. 27 (2021), 1-12. https://doi.org/10.1007/s40590-021-00328-0
  9. C. Berge, Graphs and Hypergraphs, North-Holland Pub. Co., Amsterdam, The Netherlands, 1973.
  10. C. Berge, P. Duchet, Perfect graphs and kernels, Bull. Inst. Math. Acad. Sinica 16 (1988), 263-274.
  11. M. Blidia, M. Chellali, O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005), 317-327.
  12. M. Borowiecki, M. Kuzak, On the \(k\)-stable and \(k\)-dominating sets of graphs, [in:] Graphs, Hypergraphs and Block System, Proc. Symp., Zielona Góra, 1976.
  13. M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math. 26 (2006), 5-12.
  14. R. Diestel, Graph Theory, Springer, New York, 2005.
  15. J.F. Fink, M.S. Jacobson, \(n\)-domination in graphs, [in:] Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, New York, USA, 1985, 283-300.
  16. H. Galeana-Sánchez, C. Hernández-Cruz, On the existence of \((k,l)\)-kernels in digraphs with a given circumference, AKCE Int. J. Graphs Combin 10 (2013), 15-28.
  17. H. Galeana-Sánchez, C. Hernández-Cruz, On the existence of \((k,l)\)-kernels in infinite digraphs: A survey, Discuss. Math. Graph Theory 34 (2014), 431-466. https://doi.org/10.7151/dmgt.1747
  18. R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, USA, 2011. https://doi.org/10.1201/b10959
  19. T.W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, CRC Press, 1998. https://doi.org/10.1201/9781482246582
  20. S.M. Hedetniemi, S.T. Hedetniemi, J. Knisely, D.F. Rall, Secondary domination in graphs, AKCE Int. J. Graphs Combinator. 5 (2008), 103-115.
  21. K. Kayathri, S. Vallirani, \((1,2)\)-domination in graphs, [in:] S. Arumugam, J. Bagga, L. Beineke, B. Panda (eds.), Theoretical Computer Science and Discrete Mathematics, ICTCSDM 2016, Springer, Cham, 2017. https://doi.org/10.1007/978-3-319-64419-6_17
  22. A. Kosiorowska, A. Michalski, I. Włoch, On minimum intersections of certain secondary dominating sets in graphs, Opuscula Math. 43 (2023), 813-827. https://doi.org/10.7494/opmath.2023.43.6.813
  23. M. Kucharska, On \((k,l)\)-kernel perfectness of special classes of digraphs, Discuss. Math. Graph Theory 25 (2005), 103-119. https://doi.org/10.7151/dmgt.1265
  24. S.G.H. de la Maza, C. Hernández-Cruz, On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs, Theoret. Comput. Sci. 795 (2019), 9-19. https://doi.org/10.1016/j.tcs.2019.05.031
  25. A. Meir, J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), 225-233. https://doi.org/10.2140/pjm.1975.61.225
  26. A. Michalski, P. Bednarz, On independent secondary dominating sets in generalized graph products, Symmetry 13 (2021), 2399. https://doi.org/10.3390/sym13122399
  27. A. Michalski, I. Włoch, On the existence and the number of independent \((1,2)\)-dominating sets in the \(G\)-join of graphs, Appl. Math. Comput. 377 (2020), 125155. https://doi.org/10.1016/j.amc.2020.125155
  28. A. Michalski, I. Włoch, M. Dettlaff, M. Lemańska, On proper \((1,2)\)-dominating sets, Math. Methods Appl. Sci. 45(11) (2022), 7050-7057. https://doi.org/10.1002/mma.8223
  29. O. Morgenstern, J. von Neumann, Theory of Games and Economic Behavior, Princeton University Press, Princeton, USA, 1944.
  30. J. Raczek, Polynomial algorithm for minimal \((1,2)\)-dominating set in networks, Electronics 11 (2022), 300. https://doi.org/10.3390/electronics11030300
  31. A. Włoch, On 2-dominating kernels in graphs, Australas. J. Combin. 53 (2012), 273-284.
  32. A. Włoch, I. Włoch, On \((k,l)\)-kernels in generalized products, Discrete Math. 164 (1997), 295-301. https://doi.org/10.1016/s0012-365x(96)00064-7
  33. A. Włoch, I. Włoch, On \((k,l)\)-kernels in the corona of digraphs, Int. J. Pure Appl. Math. 53 (2009), 571-582.
  34. I. Włoch, On kernels by monochromatic paths in the corona of digraphs, Open Math. 6 (2008), 537-542. https://doi.org/10.2478/s11533-008-0044-6
  • Paweł Bednarz
  • ORCID iD https://orcid.org/0000-0002-1629-0167
  • Rzeszow University of Technology, The Faculty of Mathematics and Applied Physics, Department of Discrete Mathematics, Al. Powstańców Warszawy 12, 35-029 Rzeszów, Poland
  • Adrian Michalski (corresponding author)
  • ORCID iD https://orcid.org/0000-0002-8776-5270
  • Rzeszow University of Technology, The Faculty of Mathematics and Applied Physics, Department of Discrete Mathematics, Al. Powstańców Warszawy 12, 35-029 Rzeszów, Poland
  • Natalia Paja
  • ORCID iD https://orcid.org/0000-0002-0709-6880
  • Rzeszow University of Technology, The Faculty of Mathematics and Applied Physics, Department of Discrete Mathematics, Al. Powstańców Warszawy 12, 35-029 Rzeszów, Poland
  • Communicated by Dalibor Fronček.
  • Received: 2025-07-14.
  • Revised: 2026-01-16.
  • Accepted: 2026-01-20.
  • Published online: 2026-04-10.
Opuscula Mathematica - cover

Cite this article as:
Paweł Bednarz, Adrian Michalski, Natalia Paja, On the existence of independent \((1,k)\)-dominating sets for \(k\in\{1,2\}\) in two products of graphs, Opuscula Math. 46, no. 2 (2026), 139-152, https://doi.org/10.7494/OpMath.202601201

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

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.