Opuscula Mathematica
Opuscula Math. 43, no. 6 (2023), 813-827

On minimum intersections of certain secondary dominating sets in graphs

Anna Kosiorowska
Adrian Michalski
Iwona Włoch
Abstract. In this paper we consider secondary dominating sets, also named as \((1,k)\)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the \((1,1)\)-dominating sets and proper \((1,2)\)-dominating sets. We introduce \((1,\overline{2})\)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
Keywords: dominating set, 2-dominating set, \((1,2)\)-dominating set, proper \((1,2)\)-dominating set, domination numbers, \((1,\overline{2})\)-intersection index.
Mathematics Subject Classification: 05C69, 05C76.
Full text (pdf)
References ▼
  1. [1] P. Bednarz, \((2-d)\)-kernels in the tensor product of graphs, Symmetry 2021, 13, 230. https://doi.org/10.3390/sym13020230
  2. [2] P. Bednarz, I. Włoch, On \((2-d)\)-kernels in the cartesian product of graphs, Annales Universitatis Mariae Curie-Sklodowska, Sectio A - Mathematica 70 (2016), no. 2, 1-8. https://doi.org/10.17951/a.2016.70.2.1
  3. [3] P. Bednarz, I. Włoch, An algorithm determining \((2-d)\)-kernels in trees, Util. Math. 102 (2017), 215-222.
  4. [4] P. Bednarz, C. Hernandez-Cruz, I. Włoch, On the existence and the number of \((2-d)\)-kernels in graphs, Ars Combin. 121 (2015), 341-351.
  5. [5] M. Blidia, M. Chellali, O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005), 317-327.
  6. [6] A. Bonato, T. Lidbetter, Bounds on the burning numbers of spiders and path-forests, Theoretical Computer Science 794 (2019), 12-19. https://doi.org/10.1016/j.tcs.2018.05.035
  7. [7] R. Diesel, Graph Theory, Springer-Verlag, Heidelberg, Inc., New York, 2005.
  8. [8] K.A.S. Factor, L.J. Langley, An introduction to \((1,2)\)-domination graphs, Congr. Numer. 199 (2009), 33-38.
  9. [9] J.F. Fink, M.S. Jacobson, \(n\)-domination in graphs, [in:] Graph Theory with Applications to Algorithms and Computer Science, Wiley-Intersci. Publi., Wiley, New York, 1985, 283-300.
  10. [10] P. Gupta, Domination in Graph with Application, Paripex Indian Journal of Research, 2013.
  11. [11] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
  12. [12] S.M. Hedetniemi, S.T. Hedetniemi, J. Knisely, D.F. Rall, Secondary domination in graphs, AKCE J. Graphs. Combin. 5 (2008), no. 2, 103-115.
  13. [13] C.F. de Jaenish, Trait des Applications de l'Analyse Mathematique au Jeu des Echecs, Petrograd, 1862.
  14. [14] A. Michalski, Secondary dominating sets in graph and their modification, Book of Abstracts, The 7th Gdańsk Workshop on Graph Theory, 2019.
  15. [15] A. Michalski, P. Bednarz, On independent secondary dominating sets in generalized graph products, Symmetry 2021 13, 2399.
  16. [16] 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
  17. [17] A. Michalski, I. Włoch, M. Dettlaff, M. Lemańska, On proper \((1,2)\)-dominating sets in graphs, Mathematical Models in the Applied Sciences 45 (2022), 7050-7057. https://doi.org/10.1002/mma.8223
  18. [18] O. Ore, Theory of Graphs, vol. 38, American Mathematical Society, Providence, RI, 1962.
  19. [19] A. Panpa, T. Poomsa-ard, On graceful spider graphs with at most four legs of lengths greater than one, J. Appl. Math. 2016 Article ID 5327026. https://doi.org/10.1155/2016/5327026
  20. [20] J. Raczek, Polynomial algorithm for minimal \((1,2)\)-dominating set in networks, Electronics 2022, 11, 300. https://doi.org/10.3390/electronics11030300
About the authors ▼
Anna Kosiorowska
https://orcid.org/0000-0001-6174-5266
Rzeszow University of Technology, The Faculty of Mathematics and Applied Physics, Department of Discrete Mathematics, al. Powstańców Warszawy 12, 35-959 Rzeszów, Poland
Adrian Michalski (corresponding author)
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-959 Rzeszów, Poland
Iwona Włoch
https://orcid.org/0000-0002-9969-0827
Rzeszow University of Technology, The Faculty of Mathematics and Applied Physics, Department of Discrete Mathematics, al. Powstańców Warszawy 12, 35-959 Rzeszów, Poland
About the article ▼
Communicated by Dalibor Fronček.
Received: 2022-04-23.
Revised: 2023-07-07.
Accepted: 2023-07-07.
Published online: 2023-07-22.
Cite this article as ▼
Anna Kosiorowska, Adrian Michalski, Iwona Włoch, On minimum intersections of certain secondary dominating sets in graphs, Opuscula Math. 43, no. 6 (2023), 813-827, https://doi.org/10.7494/OpMath.2023.43.6.813.
Download this article's citation as: