On graphs having proper $(1; k)$-dominating sets

Document Type : Original paper

Authors

1 LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria

2 University of Médéa, Algeria

Abstract

A (1,k)-dominating set, denoted (1,k)-dset, in a graph G=(V,E) is a set S having the property that for every vertex v in V-S, there is at least one vertex in S within distance 1 from v and a second vertex in S within distance at most k from v. A proper (1,k)-dominating set, denoted (1,k)-dset, in a graph G=(V,E) is a set D that is (1,k)-dset but not (1,k-1)-dset, meaning that D is a (1,k)-dset and there is at least one vertex v in V-D that has exactly one vertex in D within distance 1 from v, no vertices in D within distance k-1 from v and there exists at least one other vertex in D within distance k from v. The (1,k)-domination number (the proper (1,k)-domination number, respectively) of a graph G, denoted gamma_{1,k}(G) (gamma_{1,k bar}(G), respectively) is the minimum cardinality of a (1,k)-dset (a (1,k)-dset, respectively) in G. In this paper, we are interested in the study and existence of (1,k)-dsets in graphs We start by giving a characterization of graphs having (1,k)-dsets for k in {3,4}. Next, we study triangle-free graphs G with gamma_{1,k}(G)=gamma_{1,k bar}(G) for k in{3,4}. Finally, we study the complexity of the (1,k)-domination number and the (1,k bar)-domination number in bipartite graphs.

Keywords

Main Subjects

References

[1] T.J. Bean, M.A. Henning, and H.C. Swart, On the integrity of distance domination in graphs, Australas. J. Combin. 10 (1994), 29–43.
[2] A.A. Bertossi, Dominating sets for split and bipartite graphs, Inform. Process. Lett. 19 (1984), no. 1, 37–40. https://doi.org/10.1016/0020-0190(84)90126-1
[3] K.S. Booth and J.H. Johnson, Dominating sets in chordal graphs, SIAM J. Comput. 11 (1982), no. 1, 191–199. https://doi.org/10.1137/0211015
[4] G.J. Chang and G.L. Nemhauser, The $k$-domination and k-stability problems in sun-free chordal graphs, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 332–345. https://doi.org/10.1137/0605034
[5] A.K. Dewdney, Fast turning reductions between problems in N P; chapter 4; reductions between N P-complete problems, Tech. Report 71, Dep. Computer Science, Univ. Western Ontario, 1981.
[6] J.F. Fink and M.S. Jacobson, On n-domination, $n$-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer Science (1985), 301–311. https://doi.org/10.5555/21936.25447
[7] S.M. Hedetniemi, S.T. Hedetniemi, J. Knisely, D. F. Rall, and T.W. Haynes, Secondary domination in graphs, AKCE Int. J. Graphs Comb. 5 (2008), no. 2, 103–115. https://doi.org/10.1080/09728600.2008.12088856
[8] A. Kosiorowska, A. Michalski, and I. Włochh, 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
[9] A. Michalski, Secondary dominating sets in graphs and their modification, Book of Abstracts, The 7th Gda´nsk Workshop on Graph Theory, Gda´nsk, Poland, 2019.
[10] A. Michalski and 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
[11] A. Michalski, I. Włoch, M. Dettlaff, and M. Lema´nska, On proper $(1, 2)$-dominating sets in graphs, Math. Methods Appl. Sci. 45 (2022), no. 11, 7050–7057.
[12] J. Raczek, Polynomial algorithm for minimal $(1, 2)$-dominating set in networks, Electronics 11 (2022), no. 3, 300.
https://doi.org/10.3390/electronics11030300
[13] , Complexity issues on of secondary domination number, Algorithmica 86 (2024), 1163–1172. https://doi.org/10.1007/s00453-023-01192-2
Communications in Combinatorics and Optimization
Volume 11, Issue 4
Special issue in honor of Prof. Odile Favaron
December 2026
Pages 1319-1331

Files

Share

How to cite

Statistics