A central local metric dimension on acyclic and grid graph

1.   Introduction

Let $G$ be a connected graph with vertex set $V(G)$, edge set $E(G)$ and $|V(G)| = n$. The distance $d(u, v)$ in $G$ of two vertices $u$ and $v$ is the length of the shortest $u - v$ path in $G$. If there is no $u-v$ path, then $d(u, v) = \infty$ ^[1]. The eccentricity of a vertex $v$ in $G$, denoted by $e(v)$, is the distance between $u$ and a vertex farthest from $v$ in $G$, i.e., $e(v) = max\{d(u, v)\; |\; u\in V(G)\}$ ^[2]. The radius of $G$, $rad(G)$, is the smallest eccentricity among the vertices of $G$, while the largest eccentricity among the vertices of $G$ is called the diameter of $G$, $diam(G)$. The vertex $u\in V(G)$ with $e(u) = rad(G)$ is called a central vertex of $G$. For every nontrivial connected graph $G$, the radius and diameter are related by the inequality $rad(G) \leq diam (G) \leq 2rad(G)$ ^[2].

A vertex $x$ is said to resolve vertices $u$ and $v$ of $G$ if $d(x, u) \neq d(x, v)$. Let $W = \{w_1, w_2, …, w_k \}$ be a subset of $V(G)$ with $k\leq n$. The representation of $u\in V(G)$ with respect to $W$ is an ordered set

The set W is a resolving set of $G$ if and only if no two vertices of $G$ have the same representation with respect to $W$. The metric dimension of $G$, denoted by $dim(G)$, is the minimum cardinality over all resolving sets of $G$. In 1988, Slater introduced the concept of metric dimensions, which was motivated by the problem of uniquely recognizing an intruder's possible position, such as a fault in a computer network or a spoilt device ^[3]. The same concept of resolving set and metric dimension was introduced in 1976 by Harary and Melter ^[4] but using the terms locating sets and location numbers, respectively. However, several authors now have different definitions for these terms. This concept was later adopted by Chartrand et al. in 2000 ^[5] to find the upper and lower bounds of the metric dimensions of connected graphs and their properties. Since then, research related to metric dimensions has developed quite rapidly. Some of them were developed by combining the concept of metric dimension with other relevant concepts, such as complement metric dimension ^[6], fractional metric dimension ^[7], strong metric dimension ^[8], dominant metric dimension ^[9], mixed metric dimension ^[10] and edge metric dimension ^[11]. Then in 2020, Basak et al. developed the concept of metric dimension into fault-tolerant metric dimension applied to circulant graph $C(n:1, 2)$ ^[12]. Recently in 2023, Saha et al. developed the concept of fault-tolerant metric dimension by adding some parameters into optimal multi-level fault-tolerant resolving sets of circulant graph $C(n:1, 2)$ ^[13].

The concept of metric dimension involves minimizing the number of vertices on $W$ for $W\subseteq{V(G)}$, such that the distance of each vertex in $W$ to any two vertices in $G$ are different. This is similar to vertex coloring on graphs, where the number of colors needed to color vertices of a graph is minimized so that every two adjacent vertices get different colors. Using a related notion, Okamoto et al., in 2010 ^[14], developed the local metric dimension concept involving two adjacent vertices of $G$. Specifically, if two adjacent vertices of $G$ have different metric $W$ representations, then the set $W$ is a local metric generator for $G$. Moreover, the minimum cardinality of the local metric set in graph $G$ is called the local metric dimension and is denoted by $lmd(G)$ ^[14]. For a non-trivial connected graph $G$, Okamoto et al., in 2010 ^[14] showed that since every two adjacent vertices have different representations in a local metric set, then

The local metric dimension has now been studied by several authors on different graph operations or in relation to other graph parameters, which include local fractional metric dimensions ^[15], local strong metric dimensions ^[16] and dominant local metric dimensions ^[17]. Susilowati et al. has studied the similarity of metric dimension and local metric dimension. It shows that $dim_l (G) = dim(G) = n-1$ if and only if $G = K_n$ and $dim_l(G) = dim(G)$ if and only if $G = K_n$ ^[18]. The commutative characterization of graph operation with respect to metric dimension and local metric dimension has been presented in ^[19,20].

In this article, we introduce a new variant of the local metric dimension, called the central local metric dimension which combines the local metric set with all central vertices of $G$. The concept of local metric sets has applications in the analysis of chemical structural components ^[21]. Consider a scenario where one desires to identify certain sets of chemical compounds or atoms that are as central to other compounds as possible. This can be achieved by modeling with a connected graph and obtaining some information from the properties of the adjacency vertices on the chemical bound ^[14]. Moreover, the existence of central vertices in the central local metric ensemble should strengthen the implementation of the concept of local metric dimensions, not only in chemical structure but also in other domains.

The formal definition of the newly developed concept is formulated as the main result. Since the concept of metric dimensions is related to the distance between vertices in a graph, the central local metric dimension of a graph $G$ is guaranteed to exist as long as $G$ is connected. Some properties of the central local metric dimension and its consequences are discussed in the main result. We generalize in this paper the central local metric dimensions for acyclic graphs (trees) and grids. An acyclic graph is a graph that has no graph cycles and a connected acyclic graph is also known as a tree. One special tree considered in this paper is the path and star. We also use the obtained results for the path to generalize the results for grid (also known as the mesh) graphs. A grid graph, denoted as $P_n \times P_m$, is an $n\times m$ lattice graph that results from the graph Cartesian product of paths $P_n$ and $P_m$.

2.   Preliminary results

The following known results will be useful in the proof of the main results in this paper.

Theorem 2.1. ^[2] A graph $G$ is a tree if and only if every two vertices of $G$ are connected by a unique path.

Theorem 2.2. ^[22] Every tree has either one central vertex or two adjacent central vertices.

Theorem 2.3. ^[9] Let $G$ be a connected graph. If $W\subseteq{V(G)}$, then for every $v_i, v_j\in{W}$ with $i\neq{j}$, $r(v_i|W)\neq{r(v_j|W)}$.

Theorem 2.4. ^[14] Let $G$ be a connected graph:

a) If $G$ is a tree $T$, then $lmd(T) = 1$.

b) If $G$ is a path $P_n$, then $lmd(P_n) = 1$.

c) For every two connected graphs $G$ and $H$, $lmd(G\times{H}) = \max \Big\{lmd(G), lmd(H)\Big\}$.

d) If $W$ is a subset of the vertex set of $G$ containing a local metric set of $G$, then $W$ is also a local metric set of $G$.

3.   Main result

In this section, we first introduce definitions of a central set, central local metric set, central local metric basis, and central local metric dimension.

Definition 3.1. Let $G$ be a connected graph and $S\subseteq{V(G)}$. $S$ is called a central set of $G$ if the element is all central vertex of $G$ or $S = \{s\; |\; e(s) = rad(G), s\in{V(G)}\}$.

Definition 3.2. Let $W$ be an ordered set and $W\subseteq{V(G)}$. $W$ is called a central local metric set of $G$ if $W(G)$ is a local metric set and $S\subseteq{W}$. A minimal central local metric set of $G$ is called a central local metric basis of $G$ and its cardinality is called a central local metric dimension of $G$, denoted by $lmd_s (G)$.

We also construct the upper and lower bound for the central local metric dimension on Theorem 3.1.

Theorem 3.1. Let $G$ be a connected graph. If $S$ is a central set of $G$ and $W$ is a local metric set of $G$, then:

Proof. Let $G$ be a connected graph. $S$ is a central set of $G$ and $W$ is a local metric set of $G$. By Definition 3.2, $lmd_S (G)\geq |S|$ and $lmd_S (G)\geq lmd(G)$ implying that $lmd_s (G) \geq max\{|S|, lmd(G)\}$. Since the sets $S$ and $W$ are two sets that do not always intersect, $S\cup W$ is a local metric set by Theorem 2.4. Hence, $S\cup W$ is a central local metric set and $V(G)$ is always a central local metric set. Consequently, $lmd_s (G) \leq \min\Big\{|V(G)|, |S\cup W|\Big\}$. Then, $\max \Big\{|S|, lmd(G)\Big\} \leq lmd_s (G) \leq \min \Big\{|V(G)|, |S\cup W|\Big\}$. □

Since the central local metric dimension contains a central set, the properties of the central set and central local metric dimension are described as follows.

Observation 3.1. The central set of a connected graph $G$ is unique.

Lemma 3.1. Let $S$ be a central set of a connected graph $G$, $S = V(G)$ if and only if $diam(G) = rad(G)$.

Proof. Let $S = V(G)$ be a central set of $G$ and suppose that $diam(G)\neq rad(G)$. Then there is a vertex $u\in V(G)$ with $e(u)\neq rad(G)$ and $u$ is not a central vertex of $G$ or $u\notin S$. This statement is contrary to $S = V(G)$. Conversely, let $diam(G) = rad(G)$ and suppose that $S\neq V(G)$. Then, there is a vertex $u\in V(G)$ where $u$ is not a central vertex of $G$ or $u\notin S$, so $e(u)\neq rad(G)$. This statement is contrary to $diam(G) = rad(G)$. □

Lemma 3.2. Let $S$ be a central set of a connected graph $G$. If $S = V(G)$, then $S$ is a central local metric set of $G$.

Proof. Let $S$ be a central set of $G$ and $S = V(G)$. Take any two adjacent vertices $u, v\in V(G)$, since $S = V(G)$, then $u$ and $v$ also in $S$. Based on theorem 2.3, implies that $r(u|S)\neq r(v|S)$ for all $u, v\in V(G)$. So, $S$ is a central local metric set of $G$. □

Theorem 3.2. Let $G$ be a connected graph and $|V(G)| = n$, the central local metric dimension $lmd_s (G) = n$ if and only if $diam(G) = rad(G)$.

Proof. Let $G$ be a connected graph with $|V(G)| = n$ and $lmd_s(G) = n$. Suppose that $diam(G)\neq rad(G)$ then based on Lemma 3.1, $S\neq V(G)$. Let $S = \{x_1, x_2, ..., x_{n-1}\}$. Then for every two adjacent vertices $x_n\in V(G)$ and $x_i\in S$ implies $r(x_n|S)\neq r(x_i|S)$. So, $S$ is a central local metric set, and this statement is a contradiction with $lmd_s(G) = n$. Conversely, let $G$ with $V(G) = n$ and $diam(G) = rad(G)$, based on Lemma 3.1 the central set of $G$ is $S = V(G)$ and based on Lemma 3.2, $S$ is a central local metric set of $G$, then $lmd_s(G) = |V(G)| = n$. □

The graph $K_n$, $n\geq 3$, is a complete graph with vertex set $\{1, 2, ..., n\}$ ^[23]. Every vertex in $K_n$ is adjacent to every other vertex of $V(K_n)$, then $diam(K_n) = rad(K_n)$. A similar reason is applied to a complete bipartite graph $K_{m, n}$, $m, n\geq 2$ and $diam(K_{m, n}) = rad(K_{m, n})$. So, the Corollaries 1 and 2 are the consequences of Theorem 3.2.

Corollary 3.1. Let $G$ be a complete graph $K_n$, where $n\geq 3$. Then $lmd_S (G) = n$.

Corollary 3.2. Let $G$ be a complete bipartite graph $K_{m, n}$, where $m, n\geq 2$. Then $lmd_S (G) = m+n$.

The graph $C_n$, where $n\geq 3$, is a cycle with $V(C_n) = \{x_i|1\leq i\leq n\}$ and $E(C_n) = \{v_i v_{i+1}|1\leq i\leq n-1\}\cup \{v_n v_1\}$. It is easy to say that each vertex on $C_n$ has the same distance to the farthest vertex. So, $e(v_1) = e(v_2) = e(v_2) = ... = e(v_n) = \lfloor\frac{n}{2}\rfloor$. Then, $diam(C_n) = rad(C_n)$. Based on Theorem 3.2 we have a Corollary 3.3.

Corollary 3.3. Let $G$ be a cycle graph $C_n$, where $n\geq 3$. Then $lmd_S (G) = n$.

The generalized wheel graph $W_{m, n}$ when $m > 1$ and $n > 3$ is also a graph with $diam(G) = rad(G)$, then the Corollary 3.4 also a consequent from Theorem 3.2.

Corollary 3.4. Let $G$ be a generalized wheel graph $W_{m, n}$, where $m > 1$ and $n > 3$. Then $lmd_S (G) = m+n$.

Let graph $W_{m, 3}$ be a generalized wheel graph $W_{m, n}$ for $m > 1$ and $n = 3$ with $V(W_{m, 3}) = \{c_i\; |\; 1\leq i\leq m\}\cup \{x_j\; |\; 1\leq j\leq 3\}$ and $E(W_{m, 3}) = \{c_i x_j\; |\; 1\leq i\leq m, 1\leq j\leq 3\}\cup \{x_j x_{j+1}\; |\; 1\leq j\leq 2\}\cup\{x_3x_1\}$. The vertex $c_i$ adjacent with $x_j$, while the vertex $x_1$, $x_2$ and $x_3$ adjacent each other. Then, the diameter of $W_{m, 3}$ for $m > 1$ is not equal to the radius. Lemma 3.3 describe the central set of $W_{m, 3}$ and it follow by Theorem 3.3.

Lemma 3.3. Let $S$ be a central set of generalized wheel graph $W_{m, 3}$ for $m > 1$. Then $S = \{x_1, x_2, x_3\}$.

Proof. Let $S$ be a central set of $W_{m, 3}$ for $m > 1$. The vertex $c_i$, for $1\leq i\leq m$, adjacent with $x_1$, $x_2$, and $x_3$, while the vertex $x_1$, $x_2$ and $x_3$ adjacent each other. Then, the eccentricity of each vertex on $W_{m, 3}$ is $e(c_1) = e(c_2) = ... = e(c_m) = 2$ and $e(x_1) = e(x_2) = e(x_3) = 1$. Consequently, $rad(W_{m, 3}) = 1$ and $diam(W_{m, 3}) = 2$. Since $e(x_1) = e(x_2) = e(x_3) = 1 = rad(W_{m, 3})$, then $x_1$, $x_2$ and $x_3$ are the central vertices of $W_{m, 3}$. So, the central set of $W_{m, 3}$ is $S = \{x_1, x_2, x_3\}$ for $m > 1$. □

Theorem 3.3. Let $G$ be a generalized wheel graph $W_{m, 3}$ for $m > 1$. Then $lmd_s (G) = 3$.

Proof. Let $S$ be a central set of $W_{m, 3}$ for $m > 1$. Then, based on Lemma 3.3 we get $S = \{x_1, x_2, x_3\}$ and $|S| = 3$. Since the vertex $c_i$ adjacent with $x_j$, where $x_j\in S$, then $r(c_i|S)\neq r(x_j|S)$, for $1\leq i\leq m$ and $1\leq j\leq 3$. Furthermore, the vertex $x_1$, $x_2$ and $x_3$ adjacent each other, where $S = \{x_1, x_2, x_3\}$, then by Theorem 2.3, $r(x_j|S)\neq r(x_{j+1}|S)$ and $r(x_3|S)\neq r(x_1|S)$. Consequently, $S$ is a central local metric set with minimum cardinality. So, $lmd_s(W_{m, 3}) = 3$. □

Figure 1 is an example of the central local metric dimension on $W_{3, 3}$. Based on Lemma 3.3, the central local metric set of $W_{3, 3}$ is $S = \{x_1, x_2, x_3\}$. Then, $r(x_1|S) = (0, 1, 1)$, $r(x_2|S) = (1, 0, 1)$, $r(x_1|S) = (1, 1, 0)$ and $r(c_1|S) = (c_2|S) = (c_3|S) = (1, 1, 1)$ where $c_1$, $c_2$ and $c_3$ are not adjacent each other. It is easy to see that $S$ is a central local metric set of $W_{3, 3}$ and $lmd_s (W_{3, 3}) = 3$.

Furthermore, we obtain the central local metric dimension of trees. Let $T$ be a tree. By Theorem 2.2, $T$ has either only one central vertex or two adjacent central vertices. Figure 2 shows examples $T_1$ and $T_2$ of $T$ with one and two adjacent central vertices, respectively.

Given $T_1$ in Figure 2. The eccentricity of each vertices in $T_1$ are $e(v_1) = 4, e(v_2) = 4, e(v_3) = 3, e(v_4) = 2, e(v_5) = 3, e(v_6) = 3, e(v_7) = 4, e(v_8) = 4, e(v_9) = 4$ and $e(v_10) = 4$. So $diam(T_1) = 4$ and $rad(T_1) = 2$ where $e(v_4) = 2$, implying that $v_4$ is a central vertex of $T_1$. In this case, one of the longest paths in $T_1$ is $v_2-v_3-v_4-v_6-v_7$ with length 4 which contains the central vertices $v_4$.

Similarly, $T_2$ in Figure 2 has a central vertex on the longest path of $T_2$. The eccentricity of each vertices in $T_2$ are $e(u_1) = 5$, $e(u_2) = 4$, $e(u_3) = 3$, $e(u_4) = 3$, $e(u_5) = 5$, $e(u_6) = 4$, $e(u_7) = 5$, $e(u_8) = 5$, $e(u_9) = 4$, $e(u_10) = 5$ and $e(u_11) = 5$. So, $diam(T_2) = 5$ and $rad(T_2) = 3$ with $e(u_3) = 3$ and $e(u_4) = 3$. Then $u_3$ and $u_4$ are the central vertices of $T_2$. In this case, one of the longest paths in $T_2$ is $u_1-u_2-u_3-u_4-u_9-u_{10}$ with length 5, on which lies the central vertices $u_3$ and $u_4$.

From the illustrations above, it is easy to see that a central vertex of a tree $T$ lies on the longest path of $T$ whose start and end points are also endpoints in $T$. By using Theorem 2.2, we prove Lemma 3.4 which describes the position of a central vertex in a tree.

Lemma 3.4. Let $T$ be a tree. Let $u_0, u_1, …, u_k$ be a longest path in $T$ with $diam(T) = k$. Then the central set $S$ of $T$ is:

Proof. Let $T$ be a tree with $diam(T) = k$. Take any path in $T$ whose length is $k$, say, for example $u_0, u_1, …, u_k$. Since $u_0$ and $u_k$ are end vertices of this path, $e(u_0) = e(u_k) = k$. Vertices $u_1$ and $u_{k-1}$ are the second vertices after the end vertices $u_0$ and $u_k$ respectively. So, $e(u_1) = e(u_{k-1}) = k-1$. Similarly, $e(u_2) = e(u_{k-2}) = k-2$, and so on. Since $diam(T) = k$, the iteration stop on the vertex $u_\frac{k}{2}$ with $e(u_{\frac{k}{2}}) = \frac{k}{2}$ for $k$ even. So, $rad(T) = \frac{k}{2}$. However for $k$ odd, the iteration stop on vertices $u_{\lfloor{\frac{k}{2}}\rfloor}$ and $u_{\lfloor{\frac{k}{2}}+1\rfloor}$ with $e(u_{\lfloor{\frac{k}{2}}\rfloor}) = e(u_{\lfloor{\frac{k}{2}}+1\rfloor}) = \lceil{\frac{k}{2}}\rceil$. So that $rad(T) = \lceil{\frac{k}{2}}\rceil$. Therefore, the central vertices of $T$ with $diam(T) = k$ for $k$ even is $u_\frac{k}{2}$ and for $k$ odd are $u_{\lfloor{\frac{k}{2}}\rfloor}$ and $u_{\lceil{\frac{k}{2}}+1\rceil}$. Hence, the central set $S$ of $T$ with $diam(T) = k$, for k even is $S = \{u_{\frac{k}{2}}\}$ and for $k$ odd is $S = \{u_{\lfloor{\frac{k}{2}}\rfloor}, u_{\lfloor{\frac{k}{2}}+1\rfloor}\}$. □

The following Theorem 3.4 is formulated to determine the central local metric dimension of $T$.

Theorem 3.4. Let $T$ be a tree with $diam(T) = k$. The central local metric dimension, $lmd_s(T)$ of $T$ is given by

Proof.Suppose $T$ is a tree satisfying $diam(T) = k$, and $u_0, u_1, …, u_k$ is a longest path in $T$. We consider two cases.

Case 1: $k$ is even. By Lemma 3.4, the central set of $T$ is $S = \{u_{\frac{k}{2}}\}$, and $|S| = 1$. It is known from Theorem 2.4 that $lmd(T) = 1$ and from Theorem 3.1 that $lmd_s(T)\geq{1}$. Let $W = S = \{u_\frac{k}{2}\}$. By Theorem 2.1, if any two adjacent vertices $u$ and $v$ on $T$ are taken, there is a unique path between vertex $u$ and vertex $v$ to the central vertex $u_\frac{k}{2}$. Thus, it is easy to see that for the path $u, v, …, u_\frac{k}{2}$, $d(u, u_\frac{k}{2})\neq d(v, u_\frac{k}{2})$. Consequently, $r(u|W)\neq r(v|W)$, for $\forall u, v\in V(T)$ where $uv\in E(T)$. Thus, $S$ is a local metric set as well as a central set. So, $S = \{u_\frac{k}{2}\}$ is a central local metric set with minimum cardinality. Hence, $lmd_s(T) = 1$ for $T$ with $diam(T) = k$ and $k$ even.

Case 2: $k$ is odd. By Lemma 3.4, the central set of $T$ is $S = \{u_{\lfloor{\frac{k}{2}}\rfloor}, u_{\lfloor{\frac{k}{2}+1}\rfloor}\}$, and $|S| = 2$. It is known from Theorem 2.4 that $lmd(T) = 1$ and from Theorem 3.1 that $lmd_s (T)\geq{max\{|S|, lmd(T)\}} = max\{1, 2\} = {2}$, then $lmd_s (T)\geq 2$. Take $W = S = \{u_{\lfloor{\frac{k}{2}}\rfloor}, u_{\lfloor{\frac{k}{2}+1}\rfloor}\}$. By Theorem 2.1, if any two adjacent vertices $u$ and $v$ on $T$ are taken, there is a unique path between vertex $u$ and vertex $v$ to the central vertices $u_{\lfloor{\frac{k}{2}}\rfloor}$ and $u_{\lfloor{\frac{k}{2}+1}\rfloor}$. For the path $u, v, …, u_{\lfloor{\frac{k}{2}}\rfloor}, u_{\lfloor{\frac{k}{2}+1}\rfloor}$, it is easy to see that $d(u, u_{\lfloor{\frac{k}{2}}\rfloor}) \neq d(v, u_{\lfloor{\frac{k}{2}}\rfloor})$ and $d(u, u_{\lfloor{\frac{k}{2}+1}\rfloor})\neq d(v, u_{\lfloor{\frac{k}{2}+1}\rfloor})$. Thus, $r(u|W) \neq r(v|W)$ for $\forall u, v\in V(T)$ where $uv\in E(T)$. So, $S$ is a local metric set as well as a central set. Therefore, $S = \{u_{\lfloor{\frac{k}{2}}\rfloor}, u_{\lfloor{\frac{k}{2}+1}\rfloor}\}$ is a central local metric set with minimum cardinality. Then, $lmd_s (T) = 2$ for $T$ with $diam(T) = k$ and $k$ odd. □

Refer to Figure 2. The central local metric dimension of $T_1$ and $T_2$ based on Theorem 3.4 are $lmd_s(T_1) = 1$ and $lmd_s(T_2) = 2$, respectively.

The Path $P_n$ is a graph of order $n$ and size $n-1$. Let the vertex of $P_n$ labeled by $x_i$, for $1\leq i\leq n$ and the edge labeled by $x_i x_{i+1}$, for $1\leq i\leq n-1$. The diameter of $P_n$ is $diam(P_n) = n-1$. Then, the central vertex of $P_n$ when $n$ odd is $x_{\lceil \frac{n}{2} \rceil}$ and the central vertices of $P_n$ when $n$ even are $x_{\lceil \frac{n}{2} \rceil}$ and $x_{\lceil \frac{n}{2}+1 \rceil}$. Since $P_n$ is one example of a tree, based on Theorem 3.4 we have two cases for the central local metric dimension of $P_n$ as Corollary 3.5.

Corollary 3.5. If $G$ is a path graph $P_n$, then $lmd_s (G) = 1$ for $n$ odd and $lmd_s (G) = 2$ for n even.

Figure 3 is an example of the local metric dimension of path $P_n$, for $n = 5$ and $n = 6$. The vertex set of $P_5$ is $V(P_5) = \{x_1, x_2, x_3, x_4, x_5\}$ and the edge set is $E(P_5) = \{x_i x_{i+1}\; |\; 1\leq i\leq n-1\}$. Since $diam(P_5) = 4$, the central vertex is $x_3$ and the central set is $S = \{x_3\}$. Let $W = S$. Then, we have $r(x_1|W) = (2)$, $r(x_2|W) = (1)$, $r(x_3|W) = (0)$, $r(x_4|W) = (1)$, and $r(x_5|W) = (2)$. It is easy to see that $r(x_i\; |\; W)\neq r(x_{i+1}\; |\; W)$ for every two adjacent vertices $x_i$ and $x_{i+1}$ in $P_5$, $1\leq i\leq n-1$. Then, $W$ is a central local metric set with minimum cardinality and $lmd_s(P_5) = 1$. This result is consistent with Corollary 3.5. Similarly, the vertex set of $P_6$ is $V(P_6) = \{x_1, x_2, x_3, x_4, x_5, x_6\}$ and $diam(P_6) = 5$. The central Corollary 3.5, $lmd_s(P_6) = 2$.

The star $K_{1, n}$ is a graph with one central vertex and $n$ leaves. Let the central vertex of $K_{1, n}$ labeled by $c$ and the other vertex be labeled by $x_i$, for $1\leq i\leq n$. The diameter of $K_{1, n}$, for $n\geq 2$, is $diam(K_{1, n}) = 2$. Since $K_{1, n}$ is also one example of a tree, then Corollary 3.6 is a direct consequence of Theorem 3.4.

Corollary 3.6. If $G$ is a star graph $K_{1, n}$, for $n\geq 2$, then $lmd_s (G) = 1$.

Figure 4 is an example the local metric dimension of $K_{1, n}$, for $n = 6$. The vertex set of $K_{1, 6}$ is $V(K_{1, 6}) = \{c, x_1, x_2, x_3, x_4, x_5, x_6\}$ and the edge set is $E(K_{1, 6}) = \{cx_i\; |\; 1\leq i\leq 6\}$. Since the $diam(K_{1, 6}) = 2$, the central vertex of $K_{1, 6}$ is $c$ and the central set is $S = \{c\}$. Let $W = S$, then we have $r(c|W) = (0)$ and $r(x_1|W) = r(x_2|W) = ... = r(x_6|W) = (1)$ where $x_1, x_2, ..., x_6$ are not adjacent each other. It is easy to see that $r(c\; |\; W)\neq r(x_i\; |\; W)$ for every two adjacent vertices $c$ and $x_i$ in $K_{1, 6}$, $1\leq i\leq n$. Then $W$ is a central local metric set with minimum cardinality and $lmd_s(K_{1, 6}) = 1$. This result is also consistent with Corollary 3.6.

The grid graph, denoted by $P_n\times P_m$, is the graph cartesian product of path graphs $P_n$ and $P_m$. It has order $nm$ and size $(n-1)m+n$. The vertex set and edge set of $P_n\times P_m$ are, respectively $V(G) = \{v_{i, j}\; |\; 1\leq i\leq n \, \, and \, \, 1\leq j \leq m\}$ and $E(G) = \{v_{i, j}v_{i+1, j}\; |\; 1\leq i\leq n-1 \, \, and \, \, 1\leq j\leq m\}\cup \{v_{i, j}v_{i, j+1}\; |\; 1\leq i\leq n \, \, and \, \, 1\leq j\leq m-1\}$. Figure 5 is an illustration of a grid graph $P_n\times P_m$. It is clear from Figure 5 that every two adjacent vertices on $P_n\times P_m$ are not adjacent to the same vertex. To simplify the process of proving the following theorem, this condition is formulated as Observation 3.2 as follows.

Observation 3.2. There are no two adjacent vertices of $P_n\times P_m$ adjacent with the same vertex.

We know that the diameter of $P_n$ is $n-1$ and the diameter of $P_m$ is $m-1$. So, we get Observation 3.3 as follows.

Observation 3.3. The diameter of $P_n\times P_m$ is $n+m-2$.

Based on Theorem 2.4, $lmd(P_n) = 1$ and $lmd(G\times{H}) = \max \Big\{lmd(G), lmd(H)\Big\}$ for every two connected graph $G$ and $H$. Then, we get $lmd(P_n \times P_m) = \max \Big\{lmd(P_n), lmd(P_m)\Big\}$ and the Observation 3.4 holds for it.

Observation 3.4. Let $G = P_n\times P_m$. Then $lmd(G) = 1$.

We use these observations in the proof of the following lemma and theorem.

Lemma 3.5. Let $S$ be a central set of $P_n\times P_m$. Then:

Proof. Let $S$ be a central set of $P_n\times P_m$, $S_1$ be a central set of $P_n$ and $S_2$ be a central set of $P_m$. Since $diam(P_n) = n-1$, based on Lemma 3.4 we get $S_1 = \{v_{\lceil\frac{n}{2}\rceil}\}$ for $n$ odd and $S_1 = \{v_{\lceil\frac{n}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil}\}$ for $n$ even. The same applies for $P_m$ because $diam(P_n) = n-1$, then $S_2 = \{v_{\lceil\frac{m}{2}\rceil}\}$ for $m$ odd and $S_2 = \{v_{\lceil\frac{m}{2}\rceil}, v_{\lceil\frac{m}{2}+1\rceil}\}$ for $m$ even. Moreover, we consider the following cases since the grid graph is a graph resulting from the Cartesian product of two path graphs, say $P_n\times P_m$.

Case 1: $n, m$ are odd. Since $S_1 = \{v_{\lceil\frac{n}{2}\rceil}\}$ and $S_2 = \{v_{\lceil\frac{m}{2}\rceil}\}$. Vertex $v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}$ is a central vertex of $P_n\times P_m$. In line with this, by Observation 3.3, $diam(P_n\times P_m) = n+m-2$ with $e(v_{1, 1}) = e(v_{n, 1}) = e(v_{1, m}) = e(v_{n, m}) = n+m-2$. The radius of $P_n\times P_m$ is $rad(P_n\times P_m) = \lceil\frac{n}{2}\rceil$ with $e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}) = \lceil\frac{n}{2}\rceil$. So, the central set of $P_n\times P_m$ is $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}\}$, for $n, m$ odd.

Case 2: $n$ is even and $m$ is odd. Since $n$ is even and $m$ is odd, $S_1 = \{v_{\lceil\frac{n}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil}\}$ and $S_2 = \{v_{\lceil\frac{m}{2}\rceil}\}$. It is apparent from Observation 3.3 that $diam(P_n\times P_m) = n+m-2$ with $e(v_{1, 1}) = e(v_{n, 1}) = e(v_{1, m}) = e(v_{n, m}) = n+m-2$ and $rad(P_n\times P_m) = \lceil\frac{n}{2}+1\rceil$ with $e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}) = e(v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}) = \lceil\frac{n}{2}+1\rceil$. Thus, the central set of $P_n\times P_m$ is $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}\}$, for $n$ even and $m$ odd.

Case 3: $n$ is odd and $m$ is even. Since $n$ is odd and $m$ is even, $S_1 = \{v_{\lceil\frac{n}{2}\rceil}\}$ and $S_2 = \{v_{\lceil\frac{m}{2}\rceil}, v_{\lceil\frac{m}{2}+1\rceil}\}$. Similar to Case 2, we consider from Observation 3.3 that, $diam(P_n\times P_m) = n+m-2$. The radius of $P_n\times P_m$ is $rad(P_n\times P_m) = \lceil\frac{n}{2}+1\rceil$ with $e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}) = e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}) = \lceil\frac{n}{2}+1\rceil$. So, the central set of $P_n\times P_m$ for $n$ odd and $m$ even is $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}\}$.

Case 4: $n, m$ are even. Since $S_1 = \{v_{\lceil\frac{n}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil}\}$ and $S_2 = \{v_{\lceil\frac{m}{2}\rceil}, v_{\lceil\frac{m}{2}+1\rceil}\}$. The central vertices of $P_n\times P_m$ are $v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}$, $v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}$, $v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}$, and $v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil}$. In line with this, based on Observation 3.3, $diam(P_n\times P_m) = n+m-2$ and the radius of $P_n\times P_m$ is $rad(P_n\times P_m) = \lceil\frac{n}{2}+2\rceil$ with $e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}) = e(v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}) = e(v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}) = e(v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil}) = \lceil\frac{n}{2}+2\rceil$. So, the central set of $P_n\times P_m$ is $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil}\}$ for $n$ even and $m$ even. □

Recall that by Theorem 2.4, $lmd(P_n) = lmd(P_m) = 1$ in conjunction with Observation 3.4 yields $lmd(P_n\times P_m) = 1$. We prove the following theorem for the central local metric dimension on $P_n\times P_m$.

Theorem 3.5. Let $G$ be the grid graph $P_n\times P_m$.

Then,

Proof. Let $S$ be a central set of the grid graph $P_n\times P_m$. We prove the equality for different cases below.

Case 1: $n, m$ are odd. Based on Lemma 3.5 we get $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}\}$ and $|S| = 1$. Since $lmd(P_n\times P_m) = 1$ by Observation 3.4, using Theorem 3.1 we have $lmd_s (P_n\times P_m)\geq 1$. The vertex $v_{i, j}$ is adjacent to $v_{i+1, j}$ for every $v_{i, j}, v_{i+1, j}\in V(P_n\times P_m)$, where $1\leq i\leq n-1$ and $1\leq j\leq m$. By Observation 3.2, there is a path in $P_n\times P_m$ which contains vertices $v_{i, j}$, $v_{i+1, j}$, and the central vertex $v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}$ such that $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$. Consequently, $r(v_{i, j}|S)\neq r(v_{i+1, j}|S)$. Similarly, the vertex $v_{i, j}$ is adjacent to $v_{i, j+1}$ for every $v_{i, j}, v_{i, j+1}\in V(G)$, where $1\leq i\leq n$ and $1\leq j\leq m-1$. So, $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$ and $r(v_{i, j}|S)\neq r(v_{i, j+1} |S)$. Thus, $S$ is a central local metric set of $P_n\times P_m$ and $lmd_s (P_n\times P_m) = 1$, for $n, m$ odd.

Case 2: either $n$ or $m$ is odd. Let $S_1$ be the central set of $P_n\times P_m$ when $n$ even and $m$ odd and $S_2$ be the central set $P_n\times P_m$ when $n$ odd and $m$ even. Then, based on Lemma 3.5, $S_1 = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}\}$ and $S_2 = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}\}$ where $|S_1| = |S_2| = 2$. Without loss of generality, suppose $n$ is even and $m$ is odd. Then, by Observation 3.4, $lmd(P_n\times P_m) = 1$, in conjunction with Theorem 3.1 yields $lmd_s (P_n\times P_m)\geq 2$. The vertex $v_{i, j}$ is adjacent to $v_{i+1, j}$, for every $v_{i, j}, v_{i+1, j}\in V(P_n\times P_m)$ where $1\leq i\leq n-1$ and $1\leq j\leq m$. Therefore Observation 3.2 shows that there is a path in $P_n\times P_m$ which contains vertices $v_{i, j}$, $v_{i+1, j}$, and the central vertices $v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}$ and $v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}$ such that $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$ and $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})$. Consequently, $r(v_{i, j}|S_1)\neq r(v_{i+1, j}|S_1)$. Correspondingly, the vertex $v_{i, j}$ is also adjacent to $v_{i, j+1}$ for every $v_{i, j}, v_{i, j+1}\in V(P_n\times P_m)$, where $1\leq i\leq n$ and $1\leq j\leq m-1$ such that $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$ and $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})$. This then leads to the fact that $r(v_{i, j}|S_1)\neq r(v_{i, j+1}|S_1)$. Thus, $S_1 = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}\}$ is a central local metric set of $P_n\times P_m$ for $n$ even and $m$ odd. In the same way, it can be proven that $S_2 = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}\}$ is a central local metric set of $P_n\times P_m$ for $n$ odd and $m$ even. Hence, $lmd_s (P_n\times P_m) = 2$, for either $n$ or $m$ is odd.

Case 3: $n, m$ are even. Based on Lemma 3.5 we get $S = \{v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil}\}$ and $|S| = 4$. Since by Observation 3.4, $lmd(P_n\times P_m) = 1$, then in conjunction with Theorem 3.1 yields that $lmd_s (P_n\times P_m)\geq 4$. The vertex $v_{i, j}$ is adjacent to $v_{i+1, j}$, for every $v_{i, j}, v_{i+1, j}\in V(P_n\times P_m)$, where $1\leq i\leq n-1$ and $1\leq j\leq m$. Based on Observation 3.2, a path in $P_n\times P_m$ contains vertex $v_{i, j}$, vertex $v_{i+1, j}$, and all central vertices on $P_n\times P_m$. So, $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$; $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})$; $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil})$; and $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil})\neq d(v_{i+1, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil})$, implying that $r(v_{i, j}|S)\neq r(v_{i+1, j}|S)$. Similar argument applied to the vertex $v_{i, j}$ which is adjacent to $v_{i, j+1}$, for every $v_{i, j}, v_{i, j+1}\in V(P_n\times P_m)$, where $1\leq i\leq n$ and $1\leq j\leq m-1$, yields $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}\rceil})$; $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}\rceil})$; $d(v_{i, j}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}\rceil, \lceil\frac{m}{2}+1\rceil})$; and $d(v_{i, j}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil})\neq d(v_{i, j+1}, v_{\lceil\frac{n}{2}+1\rceil, \lceil\frac{m}{2}+1\rceil}$. Consequently, $r(v_{i, j}|S)\neq r(v_{i, j+1}|S)$. Thus, $S$ is a central local metric set of $P_n\times P_m$ and $lmd_s (P_n\times P_m) = 4$, for $n, m$ even. □

The ladder graph, denoted as $L_n$, is a planar graph with $2n$ vertices and $3n-2$ edges, obtained from the cartesian product of the path graphs $P_n$ and $P_2$. Thus, it is a special case of the grid graph, $P_n\times P_m$ with $m = 2$. Corollary 3.7 is a consequence of Theorem 3.5.

Corollary 3.7. Let $G$ be a ladder graph, $L_n = P_n\times P_2$. The central local metric dimension of $L_n$ is given as

Figure 6 is an example of the local metric dimension of ladder $L_n$, for $n = 5$ and $n = 6$. The vertex set and edge set of $L_5$ are, respectively $V(G) = \{v_{i, j}\; |\; 1\leq i\leq 5 \, \, and \, \, j = 1, 2\}$ and $E(G) = \{v_{i, j}v_{i+1, j}\; |\; 1\leq i\leq 4 \, \, and \, \, j = 1, 2\}\cup \{v_{i, j}v_{i, j+1}\; |\; 1\leq i\leq 5 \, \, and \, \, j = 1\}$. Based on Lemma 3.5, the central set of $L_5$ is $S = \{v_{3, 1}, v_{3, 2}\}$. Let $W = S$. Then, we have $r(v_{1, 1}|W) = (2, 3)$, $r(v_{2, 1}|W) = (1, 2)$, $r(v_{3, 1}|W) = (0, 1)$, $r(v_{4, 1}|W) = (1, 2)$, $r(v_{5, 1}|W) = (2, 3)$, $r(v_{1, 2}|W) = (3, 2)$, $r(v_{2, 2}|W) = (2, 1)$, $r(v_{3, 2}|W) = (1, 0)$, $r(v_{4, 2}|W) = (2, 1)$, and $r(v_{5, 2}|W) = (3, 2)$. It is easy to see that $r(v_{i, j}|W)\neq r(v_{i+1, j}|W)$ for every two adjacent vertices $v_{i, j}$ and $v_{i+1, j}$ and $r(v_{i, j}|W)\neq r(v_{i, j+1}|W)$ for every two adjacent vertices $v_{i, j}$ and $v_{i, j+1}$. Then, $W$ is a central local metric set with minimum cardinality and $lmd_s(L_5) = 2$. This result is consistent with Corollary 3.7. Similarly, based on Lemma 3.5, the central set of $L_6$ is $S = \{v_{3, 1}, v_{4, 1}, v_{3, 2}, v_{4, 2}\}$. Then, based on Corollary 3.7, $lmd_s(P_6) = 4$.

4.   Conclusions

This article defined a new concept, namely, the central local metric dimension of a graph. The central local metric dimension is the minimum cardinality of a local metric set that contains the central set in a graph. Thus, the lower bound of the central local metric dimension refers to the local metric dimension and the cardinality of the central set. Some properties of the central local metric dimension are presented to support future research. We get the exact values for the central local metric set of some particular classes of graphs such as cycle, complete graph, complete bipartite graph, generalized wheel graph, trees, and cartesian product of two paths. Since the central local metric dimension is a new concept, there are still many open problems for further exploration, especially in other classes of graphs.

Use of AI tools declaration

We declare that we have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The publication of this paper is funded by Center for Higher Education Fund (Balai Pembiayaan Pendidikan Tinggi), Center of Education Services (Pusat Layanan Pendidikan), and Education Fund Management Institution (LPDP), Ministry of Education, Culture, Research, and Technology of the Republic of Indonesia.

Conflict of interest

There is no conflict of interest in this research.