Opuscula Math. 43, no. 6 (2023), 813-827
https://doi.org/10.7494/OpMath.2023.43.6.813

 
Opuscula Mathematica

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)

  1. P. Bednarz, \((2-d)\)-kernels in the tensor product of graphs, Symmetry 2021, 13, 230. https://doi.org/10.3390/sym13020230
  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. P. Bednarz, I. Włoch, An algorithm determining \((2-d)\)-kernels in trees, Util. Math. 102 (2017), 215-222.
  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. M. Blidia, M. Chellali, O. Favaron, Independence and 2-domination in trees, Australas. J. Combin. 33 (2005), 317-327.
  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. R. Diesel, Graph Theory, Springer-Verlag, Heidelberg, Inc., New York, 2005.
  8. K.A.S. Factor, L.J. Langley, An introduction to \((1,2)\)-domination graphs, Congr. Numer. 199 (2009), 33-38.
  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. P. Gupta, Domination in Graph with Application, Paripex Indian Journal of Research, 2013.
  11. T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
  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. C.F. de Jaenish, Trait des Applications de l'Analyse Mathematique au Jeu des Echecs, Petrograd, 1862.
  14. A. Michalski, Secondary dominating sets in graph and their modification, Book of Abstracts, The 7th Gdańsk Workshop on Graph Theory, 2019.
  15. A. Michalski, P. Bednarz, On independent secondary dominating sets in generalized graph products, Symmetry 2021 13, 2399.
  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. 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. O. Ore, Theory of Graphs, vol. 38, American Mathematical Society, Providence, RI, 1962.
  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. J. Raczek, Polynomial algorithm for minimal \((1,2)\)-dominating set in networks, Electronics 2022, 11, 300. https://doi.org/10.3390/electronics11030300
  • Anna Kosiorowska
  • ORCID iD 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)
  • 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-959 Rzeszów, Poland
  • Iwona Włoch
  • ORCID iD 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
  • Communicated by Dalibor Fronček.
  • Received: 2022-04-23.
  • Revised: 2023-07-07.
  • Accepted: 2023-07-07.
  • Published online: 2023-07-22.
Opuscula Mathematica - cover

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:
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.