TY - JOUR

T1 - A STUDY OF A COMBINATION OF DISTANCE DOMINATION AND RESOLVABILITY IN GRAPHS

AU - Retnowardani, Dwi Agustin

AU - Utoyo, Mohammad Imam

AU - Dafik,

AU - Susilowati, Liliek

AU - Dliou, Kamal

N1 - Publisher Copyright:
© 2024 University of Zielona Gora. All rights reserved.

PY - 2024

Y1 - 2024

N2 - 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 γkension of the graph G, denoted by γk(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 r k(G). We give several bounds for r k(G), some in terms of the metric γkension γk(G) and the distance k-domination number k(G). We determine r k(G) when G is a path or a cycle. Afterwards, we characterize the connected graphs of order n having r k(G) equal to 1, n - 2, and n - 1, for k ≥ 2. Then, we construct graphs realizing all the possible triples (γk(G), k(G), r k(G)), for all k ≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number r k(G) = r k ≥ 1, we provide graphs achieving this maximum order for any positive integers k and r k. Then, we establish Nordhaus-Gaddum bounds for r k(G), for k ≥ 2. Finally, we give relations between r k(G) and the k-truncated metric γkension of graphs and give some directions for future work.

AB - 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 γkension of the graph G, denoted by γk(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 r k(G). We give several bounds for r k(G), some in terms of the metric γkension γk(G) and the distance k-domination number k(G). We determine r k(G) when G is a path or a cycle. Afterwards, we characterize the connected graphs of order n having r k(G) equal to 1, n - 2, and n - 1, for k ≥ 2. Then, we construct graphs realizing all the possible triples (γk(G), k(G), r k(G)), for all k ≥ 2. Later, we determine the maximum order of a graph G having distance k-resolving domination number r k(G) = r k ≥ 1, we provide graphs achieving this maximum order for any positive integers k and r k. Then, we establish Nordhaus-Gaddum bounds for r k(G), for k ≥ 2. Finally, we give relations between r k(G) and the k-truncated metric γkension of graphs and give some directions for future work.

KW - distance k-domination

KW - distance k-resolving domination

KW - metric γkension

KW - resolving set

UR - http://www.scopus.com/inward/record.url?scp=85193298365&partnerID=8YFLogxK

U2 - 10.7151/dmgt.2484

DO - 10.7151/dmgt.2484

M3 - Article

AN - SCOPUS:85193298365

SN - 1234-3099

VL - 44

SP - 1051

EP - 1078

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 3

ER -