Opuscula Math. 45, no. 1 (2025), 53-62
https://doi.org/10.7494/OpMath.2025.45.1.53
Opuscula Mathematica
(1,2)-PDS in graphs with the small number of vertices of large degrees
Abstract. 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\).
Keywords: domination, secondary domination, neighborhoods, maximum degree.
Mathematics Subject Classification: 05C69, 05C76.
- C. Berge, The Theory of Graphs and its Applications, New York, Wiley, 1962.
- A. Cabrera-Martinez, A. Estrada-Moreno, Double domination in rooted product graphs, Discrete Appl. Math. 339 (2023), 127-135. https://doi.org/10.1016/j.dam.2023.06.021
- E.J. Cockayne, S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247-261. https://doi.org/10.1002/net.3230070305
- R. Diestel, Graph Theory, Springer-Verlag, Heidelberg, New York, 2005.
- A. Hansberg, L. Volkmann, On graphs with equal domination and 2-domination numbers, Discrete Math. 308 (2008), no. 11, 2277-2281. https://doi.org/10.1016/j.disc.2007.04.057
- J. Harant, M.A. Henning, On double domination in graphs, Discuss. Math. Graph Theory 25 (2005), 29-34. https://doi.org/10.7151/dmgt.1256
- S.M. Hedetniemi, S.T. Hedetniemi, D.F. Rall, J. Knisely, Secondary domination in graphs, AKCE Int. J. Graphs Comb. 5 (2008), 117-125.
- C. Hoppen, G. Mansan, Minimum 2-dominating sets in regular graphs, Discrete Appl. Math. 323 (2022), 268-285. https://doi.org/10.1016/j.dam.2022.01.002
- C.F. de Jaenisch, Traite des applications de l’analyse mathematique au jeu desechecs, St. Petersbourg Academie Imperiale des Sciences, 1862.
- 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. https://doi.org/10.1007/978-3-319-64419-6_17
- 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. https://doi.org/10.7494/opmath.2023.43.6.813
- A. Michalski, Secondary dominating sets in graphs and their modification, Book of Abstracts, The 7th Gdańsk Workshop on Graph Theory (2019).
- A. Michalski, P. Bednarz, On independent secondary dominating sets in generalized graph products, Symmetry 2021, 13, 2399. https://doi.org/10.3390/sym13122399
- 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
- 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. https://doi.org/10.1002/mma.8223
- O. Ore, Theory of Graphs, vol. 38, Amer. Math. Soc., 1962. https://doi.org/10.1090/coll/038
- J. Raczek, Polynomial algorithm for minimal \((1, 2)\)-dominating set in networks, Electronics 2022, 11, 300. https://doi.org/10.3390/electronics11030300
- J. Raczek, Complexity issues on of secondary domination number, Algorithmica 86 (2024), 1163-1172. https://doi.org/10.1007/s00453-023-01192-2
- Urszula Bednarz (corresponding author)
https://orcid.org/0000-0002-4856-9613- 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
- Mateusz Pirga
- 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: 2024-05-08.
- Revised: 2024-10-23.
- Accepted: 2024-10-30.
- Published online: 2024-12-20.
