Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 11 4 2026 12 01 On graphs having proper $(1; k)$-dominating sets 1319 1331 15194 10.22049/cco.2026.31244.2794 EN Mostafa Blidia LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria Ahmed Bouchou LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria University of Médéa, Algeria Journal Article 2025 11 21 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. https://comb-opt.azaruniv.ac.ir/article_15194_0a8f395097cc4ce96161e9d9e461024a.pdf