On minimum intersections of certain secondary dominating sets in graphs

• Autorzy: Kosiorowska Anna , Michalski Adrian , Włoch Iwona

Identyfikatory

DOI

10.7494/OpMath.2023.43.6.813

• Języki publikacji: EN

Abstrakty

EN

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,2)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.

Słowa kluczowe

EN

dominating set; 2-dominating set; (1, 2)-dominating set; proper (1, 2)-dominating set; domination number; (1,2)-intersection index

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 6
• Strony: 813--827
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Kosiorowska Anna

• 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

• https://orcid.org/0000-0001-6174-5266

autor

Michalski Adrian

• 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

• https://orcid.org/0000-0002-8776-5270

autor

Włoch Iwona

• 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

• https://orcid.org/0000-0002-9969-0827

Bibliografia

• [1] P. Bednarz, On (2−d)-kernels in the tensor product of graphs, Symmetry 2021, 13, 230.
• [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.
• [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.
• [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.
• [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.
• [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.
• [20] J. Raczek, Polynomial algorithm for minimal (1, 2)-dominating set in networks, Electronics 2022, 11, 300.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)