(1,2)-PDS in graphs with the small number of vertices of large degrees

• Autorzy: Bednarz Urszula , Pirga Mateusz

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.53

• Języki publikacji: EN

Abstrakty

EN

We define and study a perfect (1, 2)-dominating set which is a special case of a (1, 2)-dominating set. We discuss the existence of a perfect (1, 2)-dominating set in graphs with at most two vertices of maximum degree. In particular, we present a complete solution if the maximum degree equals n − 1 or n − 2.

Słowa kluczowe

EN

domination; secondary domination; neighborhoods; maximum degree

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 53--62
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Bednarz Urszula

• 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-4856-9613

autor

Pirga Mateusz

• 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

Bibliografia

• [1] C. Berge, The Theory of Graphs and its Applications, New York, Wiley, 1962.
• [2] A. Cabrera-Martinez, A. Estrada-Moreno, Double domination in rooted product graphs, Discrete Appl. Math. 339 (2023), 127–135.
• [3] E.J. Cockayne, S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247–261.
• [4] R. Diestel, Graph Theory, Springer-Verlag, Heidelberg, New York, 2005.
• [5] A. Hansberg, L. Volkmann, On graphs with equal domination and 2-domination numbers, Discrete Math. 308 (2008), no. 11, 2277–2281.
• [6] J. Harant, M.A. Henning, On double domination in graphs, Discuss. Math. Graph Theory 25 (2005), 29–34.
• [7] S.M. Hedetniemi, S.T. Hedetniemi, D.F. Rall, J. Knisely, Secondary domination in graphs, AKCE Int. J. Graphs Comb. 5 (2008), 117–125.
• [8] C. Hoppen, G. Mansan, Minimum 2-dominating sets in regular graphs, Discrete Appl. Math. 323 (2022), 268–285.
• [9] C.F. de Jaenisch, Traite des applications de l’analyse mathematique au jeu desechecs, St. Petersbourg Academie Imperiale des Sciences, 1862.
• [10] 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, Springer, Cham, 2017, 128–133.
• [11] A. Kosiorowska, A. Michalski, I. Włoch, On minimum intersections of certain secondary dominating sets in graphs, Opuscula Math. 43 (2023), no. 6, 813–827.
• [12] A. Michalski, Secondary dominating sets in graphs and their modification, Book of Abstracts, The 7th Gdańsk Workshop on Graph Theory (2019).
• [13] A. Michalski, P. Bednarz, On independent secondary dominating sets in generalized graph products, Symmetry 2021, 13, 2399.
• [14] 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.
• [15] A. Michalski, I. Włoch, M. Dettlaff, M. Lemańska, On proper (1, 2)-dominating sets in graphs, Math. Methods Appl. Sci. 45 (2022), no. 11, 7050–7057.
• [16] O. Ore, Theory of Graphs, vol. 38, Amer. Math. Soc., 1962.
• [17] J. Raczek, Polynomial algorithm for minimal (1, 2)-dominating set in networks, Electronics 2022, 11, 300.
• [18] J. Raczek, Complexity issues on of secondary domination number, Algorithmica 86 (2024), 1163–1172.