2021/11/17 by Dwi Agustin Retnowardani, Retnowardani, Dwi Agustin, Muhammad Imam Utoyo +7
Computer Science · #05C12 #05C69 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2111.09095
openalex publication_date 2021/11/17 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
For k ≥ 1, in a graph G=(V,E), a set of vertices D is a distance k-dominating set of G, if any vertex in V∖ D is at distance at most k from some vertex in D. The minimum cardinality of a distance k-dominating set of G is the distance k-domination number, denoted by γk(G). An ordered set of vertices W=\w1,w2,…,wr\ is a resolving set of G, if for any two distinct vertices x and y in V∖ W, there exists 1≤ i≤ r, such that dG(x,wi)≠ dG(y,wi). The minimum cardinality of a resolving set of G is the metric dimension of the graph G, denoted by dim(G). In this paper, we introduce the distance k-resolving dominating set, which is a subset of V that is both a distance k-dominating set and a resolving set of G. The minimum cardinality of a distance k-resolving dominating set of G is called the distance k-resolving domination number and is denoted by γrk(G). We give several bounds for γrk(G) some in terms of the metric dimension dim(G) and the distance k-domination number γk(G). We determine γrk(G) when G is a path or a cycle. Afterwards, we characterize the connected graphs of order n having γrk(G) equal to 1, n-2, and n-1, for k≥ 2. Then, we construct graphs realizing all the possible triples (dim(G),γk(G),γrk (G)), for all k≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number γrk(G)=γrk≥ 1, we provide graphs achieving this maximum order for any positive integers k and γrk. Finally, we establish Nordhaus-Gaddum bounds for γrk(G), for k≥ 2.