I Wayan Sudarsana^∗a , Faisal Susanto^b , Selvy Musdalifah^a

^aAlgebra and Combinatorics Research Group (ACRG), Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Tadulako, Indonesia ^bDoctoral Program of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

sudarsanaiw1972@gmail.com, faisalsusanto16@gmail.com, selvymusdalifah@yahoo.com

Let c : V (G) → {1, 2, . . . , k} be a proper k-coloring of a simple connected graph G. Let Π = {C1, C2, . . . , Ck} be a partition of V (G), where Cⁱ is the set of vertices of G receiving color i. The color code, cΠ(v), of a vertex v with respect to Π is an ordered k-tuple (d(v, C2), d(v, C2), . . . , d(v, Ck)), where d(v, Ci) = min{d(v, x) : x ∈ Ci} for i = 1, 2, . . . , k. If distinct vertices have distinct color codes then c is called a locating coloring of G. The minimum k for which c is a locating coloring is the locating chromatic number of G, denoted by χL(G). Let G be a non trivial connected graph and let m ≥ 2 be an integer. The m-shadow of G, denoted by Dm(G), is a graph obtained by taking m copies of G, say G1, G2, . . . , Gm, and each vertex v in Gⁱ , i = 1, 2, . . . , m−1, is joined to the neighbors of its corresponding vertex v ′ in Gi+1. In the present paper, we deal with the locating chromatic number for m-shadow of connected graphs. Sharp bounds on the locating chromatic number of Dm(G) for any non trivial connected graph G and any integer m ≥ 2 are obtained. Then the values of locating chromatic number for m-shadow of complete multipartite graphs and paths are determined, some of which are considered to be optimal.

Keywords: locating chromatic number, m-shadow of graphs, locating coloring, complete multipartite graph, path Mathematics Subject Classification : 05C12, 05C15

DOI: 10.5614/ejgta.2022.10.2.18

Received: 11 May 2022, Revised: 14 September 2022, Accepted: 9 October 2022.

^*corresponding author

1. Introduction

All graphs considered in this paper are only connected, finite and undirected containing no loops nor multiple edges. Let G=(V(G),E(G)) be a graph with vertex set V(G) and edge set E(G). We use \(P_n\) to denote a path of order n and \(K_{n_1,n_2,\ldots,n_r}\) to denote a complete r-partite graph where \(n_i \leq n_j\) for i < j. A complete graph on n vertices and a star on n+1 vertices are denoted by \(K_n\) and \(K_{1,n}\), respectively. For \(u,v \in V(G)\) and a non negative integer k, a u-v walk of length k is a sequence of vertices \((u=v_0,v_1,\ldots,v_k=v)\), where \(v_iv_{i+1}\) is an edge of G for every \(i=0,1,\ldots,k-1\). When no vertex is repeated in the sequence, it is called a u-v path. The distance between u and v, denoted by \(d_G(u,v)\) (or d(u,v) in short), is defined as the length of the shortest u-v path.

Let \(c:V(G) \to \{1,2,\ldots,k\}\) be a proper k-coloring of G and let \(\Pi=\{C_1,C_2,\ldots,C_k\}\) be a partition of V(G), where \(C_i\) is the set of vertices in G receiving color i. The color code \(c_{\Pi}(v)\) of v with respect to \(\Pi\) is an ordered k-tuple \((d(v,C_1),d(v,C_2),\ldots,(v,C_k))\), where \(d(v,C_i)=\min\{d(v,x):x\in C_i\}\) for \(i=1,2,\ldots,k\). If distinct vertices have distinct color codes then c is called a locating k-coloring of G. The locating chromatic number of G, denoted by \(\chi_L(G)\), is the minimum k for which c is a locating coloring.

The concept of locating chromatic number of graphs was introduced in 2002 by Chartrand et al. [15] as a combination of two concepts in graph theory namely graph coloring and partition dimension of graphs. Computing the locating chromatic number for general graphs is an NPcomplete. It means that there is no efficient algorithm of calculating the locating chromatic number for a general graph. However, a number of researches restricted on specific classes of graphs have been carried out. For instance, the locating chromatic number for some families of graphs has been found such as paths, cycles, complete multipartite, and bistars in [15], amalgamation of stars in [3], firecracker graphs in [4], Barbell graphs in [5], Kneser graphs in [12], powers of paths and cycles in [17], book graphs in [19], Origami graphs in [20], and Möobius ladder graphs in [21]. Characterizations of graphs having certain locating chromatic number were studied such as trees with locating chromatic number 3 in [8], trees of order n with locating chromatic number n-tfor \(2 \le t < \frac{n}{2}\) in [22], unicyclic graphs of order n with locating chromatic number n-3 or n-2in [2, 7], and graphs of order n with locating chromatic number n-1 in [14]. In [10, 11, 13], it was investigated the locating chromatic number for the join product, Cartesian product and corona product of graphs. Recently, some upper bounds for the locating chromatic number of trees were also developed by some authors (see [6, 9, 16, 18]).

In [1], Agustin et al. defined an m-shadow of a graph as follows. Let G be a non trivial connected graph and let an integer \(m \geq 2\) be given. The m-shadow of G, denoted by \(D_m(G)\), is a graph obtained by taking m copies of G, say \(G_1, G_2, \ldots, G_m\), and each vertex v in \(G_i\), \(i = 1, 2, \ldots, m-1\), is joined to the neighbors of its corresponding vertex v' in \(G_{i+1}\).

In this paper, we study the locating chromatic number for m-shadow of a connected graph. We give sharp lower and upper bound of the parameter \(\chi_L(G)\) for m-shadow of any non trivial connected graph. The values of locating chromatic number for m-shadow of complete multipartite graphs and paths are then determined, some of which are considered to be optimal.

2. Lower and upper bound

We begin with the following result that will be used later.

Proposition 2.1. Let \(u_i \in V(G_i)\) and \(v_j \in V(G_j)\), \(i \neq j\), be two vertices of \(H \cong D_m(G)\) corresponding to vertices u and v in G, respectively. Then

\[d_H(u_i, v_j) = \begin{cases} |i - j|, & \text{if there exists a } u - v \text{ walk of length } |i - j| \text{ in } G, \\ \max\{d_G(u, v), |i - j| + 1\}, & \text{otherwise.} \end{cases}\]

Proof. For each \(u,v\in V(G)\), let \((u=x^0,x^1,\ldots,x^k=v)\) be a u-v walk of length k in G. Let \(H\cong D_m(G)\). Consider two vertices \(u_i,v_j\in V(H),\,i\neq j\), with \(u_i\in V(G_i)\) and \(v_j\in V(G_j)\), corresponding to u and v in G, respectively. Say, without loss of generality, i< j. Let k=|i-j|. Then \((u_i=x_i^0,x_{i+1}^1,\ldots,x_j^k=v_j)\) is a \(u_i-v_j\) path of length k in H. So \(d_H(u_i,v_j)=|i-j|\). Now suppose \(k\neq |i-j|\). We have two cases.

Case 1. \(d_G(u,v) > |i-j|\). Then \(d_G(u,v) = \max\{d_G(u,v), |i-j|+1\}\). So \((u_i = x_i^0, x_{i+1}^1, \dots, x_j^{|i-j|}, x_j^{|i-j|+1}, \dots, x_j^{d_G(u,v)} = v_j)\) is a \(u_i - v_j\) path of length \(d_G(u,v)\) in H. Thus \(d_H(u_i, v_j) = d_G(u, v)\).

Case 2. \(d_G(u,v) < |i-j|\). Then \(|i-j|+1 = \max\{d_G(u,v), |i-j|+1\}\). Suppose that w is a vertex adjacent to v in G. Then \((u_i = x_i^0, x_{i+1}^1, \dots, x_{i+d_G(u,v)}^{d_G(u,v)} = v_{i+d_G(u,v)})\) is a \(u_i - v_{i+d_G(u,v)}\) path of length \(d_G(u,v)\) in H and \((v_{i+d_G(u,v)}, w_{i+d_G(u,v)+1}, v_{i+d_G(u,v)+2}, w_{i+d_G(u,v)+3}, \dots, v_{j-1}, w_j, v_j)\) is a \(v_{i+d_G(u,v)} - v_j\) path of length \(j - i - d_G(u,v) + 1\) in H. Hence

\[d_H(u_i, v_j) \le d_G(u, v) + j - i - d_G(u, v) + 1 = |i - j| + 1.\] (1)

As \(k \neq |i - j|\),

\[d_H(u_i, v_j) \ge |i - j| + 1.\] (2)

By (1) and (2), \[d_H(u_i, v_j) = |i - j| + 1\].

The next theorem presents the bounds on the locating chromatic number for m-shadow of a connected graph G.

Theorem 2.1. Let G be a non trivial connected graph and m > 2. Then

\[\chi_L(G) + 1 \le \chi_L(D_m(G)) \le 2\chi_L(G).\]

Proof. First, we will prove the lower bound. We here will use a contradiction strategy. Thus, assume that \(\chi_L(D_m(G)) = \chi_L(G)\). Consider the first and the second copy of G in the graph \(D_m(G)\), i.e., \(G_1\) and \(G_2\), respectively. If there is no mutual color used in \(G_1\) and \(G_2\), then the number of colors used in \(G_1\) must be less than \(\chi_L(G)\) and number of colors used in \(G_2\) must be less than \(\chi_L(G)\). By definition of locating coloring, at least two vertices in \(G_1\) or \(G_2\) belonging to the same color class have the same color codes, a contradiction. Suppose that at least one mutual color is used in \(G_1\) and \(G_2\). Then there must be two vertices in \(G_1 \cup G_2\) belonging to the same color class having the same color codes, a contradiction. Thus \(\chi_L(D_m(G)) \geq \chi_L(G) + 1\).

Next, we will prove the upper bound. Let us denote by the symbol \(v_i\), \(i=1,2,\ldots,m\), a vertex in \(G_i\), \(G_i \subset D_m(G)\), corresponding to the vertex v in G. Define a coloring c on the vertices of \(D_m(G)\) in the following way. Let \(c(v_m) = c'(v) + \chi_L(G)\), and \(c(v_i) = c'(v)\) for \(i=1,2,\ldots,m-1\), where c' is a locating \(\chi_L(G)\)-coloring of G.

We show that c is a locating coloring of \(D_m(G)\). To do so, it suffices to show that every two distinct vertices \(u_i\) and \(v_j\) of \(D_m(G)\) in each color class have distinct color codes. If \(1 \leq i = j \leq m\) then \(c_{\Pi}(u_i) \neq c_{\Pi}(v_j)\) since c' is a locating coloring of G. Let us consider \(1 \leq i < j \leq m-1\). First, let \(j-i \geq 2\). We have \(d_{D_m(G)}(u_i,v_m) \geq m-i \geq m-j+2 > m-j+1 \geq d_{D_m(G)}(v_j,v_m)\). Then \(u_i\) and \(v_j\) are distinguished by the color class \(C_{\chi_L(G)+c(v_j)}\). Now let j-i=1. By Proposition \(2.1, m-j \leq d_{D_m(G)}(v_j,v_m) \leq m-j+1\). If \(d_{D_m(G)}(v_j,v_m) = m-j\) then \(d_{D_m(G)}(u_i,v_m) \geq m-i=m-j+1 > m-j=d_{D_m(G)}(v_j,v_m)\). So \(u_i\) and \(v_j\) are distinguished by the color class \(C_{\chi_L(G)+c(v_j)}\). If \(d_{D_m(G)}(v_j,v_m) = m-j+1\) then \(d_{D_m(G)}(v_j,w_m) = m-j\), where \(w_m\) is a vertex in \(G_m\) adjacent to \(v_m\). We get \(d_{D_m(G)}(u_i,w_m) \geq m-j+1 > m-j=d_{D_m(G)}(v_j,w_m)\). So \(u_i\) and \(v_j\) are distinguished by the color class \(C_{\chi_L(G)+c(w_j)}\). Thus all the vertices have distinct color codes and the proof is concluded.

As we will see the results in (3), (4) and Lemma 4.1, the bounds in Theorem 2.1 are sharp.

3. The m-shadow of complete multipartite graphs

Let \(G \cong D_m(K_{n_1,n_2,\dots,n_r})\) be the m-shadow of a complete r-partite graph consisting of mr vertex subsets namely \(V_1^1,V_1^2,\dots,V_1^r,V_2^1,V_2^2,\dots,V_2^r,\dots,V_m^1,V_m^2,\dots,V_m^r\) such that \(|V_i^j|=n_j\) for \(i=1,2,\dots,m\) and \(j=1,2,\dots,r\), which form a partition in G. The graph G has vertex set \(V(G)=\bigcup_{i=1}^m\bigcup_{j=1}^rV_i^j\), where \(V_i^j=\{v_{i,k}^j:j=1,2,\dots,r \text{ and } k=1,2,\dots,n_j\}\) is the jth partite in the ith copy of \(K_{n_1,n_2,\dots,n_r}\).

It was proved in [15] that \(\chi_L(K_{n_1,n_2,\dots,n_r}) = \sum_{z=1}^r n_z\). Since the 2-shadow of a complete r-partite \(K_{n_1,n_2,\dots,n_r}\) is a complete r-partite graph \(K_{2n_1,2n_2,\dots,2n_r}\), we have

\[\chi_L(D_2(K_{n_1,n_2,\dots,n_r})) = 2\sum_{z=1}^r n_z.\] (3)

Let us consider the graph \(D_m(K_{n_1,n_2,\dots,n_r})\), for \(m \geq 3\). In this case, we claim that it is not possible to attain the lower bound in Theorem 2.1. We need to add at least one more color in order to produce a locating coloring. The next lemma proves our claim. Please note that every proper \(\sum_{z=1}^r n_z\)-coloring of \(D_m(K_{n_1,n_2,\dots,n_r})\) has the property that for every \(1 \leq i \neq i' \leq m\) and \(1 \leq j \leq r\), the sets of colors used to color the vertices on \(V_i^j\) are the same as those used to color the vertices on \(V_{i'}^j\).

Lemma 3.1. Let \[m \geq 3\], \(r \geq 2\) and \(n_1 \leq n_2 \leq \cdots \leq n_r\). Then \(\chi_L(D_m(K_{n_1,n_2,...,n_r})) \geq \sum_{z=1}^r n_z + 2\).

Proof. It suffices to show that there is no locating \((\sum_{z=1}^r n_z + 1)\)-coloring of \(D_m(K_{n_1,n_2,\dots,n_r})\). Assume that such a coloring c exists. The vertex \((\sum_{z=1}^r n_z + 1)\)-coloring c of \(D_m(K_{n_1,n_2,\dots,n_r})\) can be obtained from the vertex \(\sum_{z=1}^r n_z\)-coloring of \(D_m(K_{n_1,n_2,\dots,n_r})\) by replacing 'old' color of at least one vertex with the 'new' color \(\sum_{z=1}^r n_z + 1\). Say, the color \(c_0\) of

\(v_{i,k}^j \in V_i^j\) for some \(c_0, i, j, k\), is replaced with the color \(\sum_{z=1}^r n_z + 1\). As c is proper, the sets of colors used to color the vertices in \(V_{i-1}^{j'}, V_i^{j'}\) and \(V_{i+1}^{j'}\) for every \(j', 1 \leq j' \neq j \leq r\), are not replaced. This implies that at least two vertices in \(V_{i-1}^{j'} \cup V_i^{j'} \cup V_{i+1}^{j'}\) belonging to the same color class have the same color codes, a contradiction. Thus \(\chi_L(D_m(K_{n_1,n_2,\ldots,n_r})) \geq \sum_{z=1}^r n_z + 2\).

Lemma 3.2. Let \(r \geq 2\) and \(2 \leq n_1 \leq n_2 \leq \cdots \leq n_r\). Then \(\chi_L(D_3(K_{n_1,n_2,\dots,n_r})) \leq \sum_{z=1}^r n_z + 3\).

Proof. Define a vertex \((\sum_{z=1}^r n_z + 3)\)-coloring c of \(D_3(K_{n_1,n_2,\dots,n_r})\) in the following way. Let \(c(v_{1,n_1}^1) = c(v_{3,n_2}^2) = \sum_{z=1}^r n_z + 1\), \(c(v_{1,n_2}^2) = \sum_{z=1}^r n_z + 2\) and \(c(v_{3,n_1}^1) = \sum_{z=1}^r n_z + 3\). Next, let \(c(v_{i,k}^j) = \sum_{z=1}^{j-1} n_z + k\) for \(i = 1, 2, 3, j = 1, 2, \dots, r\) and \(k = 1, 2, \dots, n_j\), where \((i, k) \neq (1, n_1), (3, n_1), (1, n_2)\) or \((3, n_2)\). It is easy to see that c is a locating coloring.

Lemma 3.3. Let \(r \geq 2\) and \(2 \leq n_1 \leq n_2 \leq \cdots \leq n_r\). Then \(\chi_L(D_4(K_{n_1,n_2,\dots,n_r})) \leq \sum_{z=1}^r n_z + 3\).

Proof. Define a vertex \((\sum_{z=1}^r n_z + 3)\)-coloring c of \(D_4(K_{n_1,n_2,\dots,n_r})\) as follows. Let \(c(v_{1,n_1}^1) = \sum_{z=1}^r n_z + 1\), \(c(v_{2,n_1}^1) = c(v_{4,n_2}^2) = \sum_{z=1}^r n_z + 2\) and \(c(v_{3,n_2}^2) = \sum_{z=1}^r n_z + 3\). Next, let \(c(v_{i,k}^j) = \sum_{z=1}^{j-1} n_z + k\) for \(i = 1, 2, \dots, 4\), \(j = 1, 2, \dots, r\) and \(k = 1, 2, \dots, n_j\), where \((i, k) \neq (1, n_1), (2, n_1), (3, n_2)\) or \((4, n_2)\). It is not hard to show that c is a locating coloring. \(\square\)

Lemma 3.4. Let \(m \geq 3\), \(r \geq 2\) and \(1 = n_1 \leq n_2 \leq \cdots \leq n_r\). Then \(\chi_L(D_m(K_{n_1,n_2,\dots,n_r})) = \sum_{z=1}^r n_z + 2\).

Proof. Due to Lemma 3.1, it is sufficient to show the existence of a locating \((\sum_{z=1}^r n_z + 2)\)-coloring of \(D_m(K_{n_1,n_2,\dots,n_r})\). Let us define a coloring \(c:V(D_m(K_{n_1,n_2,\dots,n_r})) \to \{1,2,\dots,\sum_{z=1}^r n_z + 2\}\) in the following way.

\[\begin{split} c(v_{i,1}^1) &= 1 \quad \text{for } i = 1, 2, \dots, m-2, \\ c(v_{i,1}^1) &= \sum_{z=1}^r n_z - m + 2 + i \quad \text{for } i = m-1, m, \\ c(v_{i,k}^j) &= \sum_{z=1}^{j-1} n_z + k \quad \text{for } i = 1, 2, \dots, m, \ j = 2, 3, \dots, r \ \text{and} \ k = 1, 2, \dots, n_j. \end{split}\]

Let u and v be any two vertices of \(D_m(K_{n_1,n_2,...,n_r})\) such that u and v belong to the same color class. Consider the following cases.

• If \(u = v_{i,k}^j\) and \(v = v_{i',k}^j\) for \(1 \le i \ne i' \le m-1\), \(2 \le j \le r\) and \(1 \le k \le n_j\) then \(c_\Pi(u) \ne c_\Pi(v)\) since \(d(u, C_{\sum_{z=1}^r n_z + 2}) \ne d(v, C_{\sum_{z=1}^r n_z + 2})\).
• If \(u=v_{i,k}^j\) and \(v=v_{m,k}^j\) for \(1 \le i \le m-1\), \(2 \le j \le r\) and \(1 \le k \le n_j\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u,C_1) \ne d(v,C_1)\).
• If \(u = v_{i,1}^1\) and \(v = v_{i',1}^1\) for \(1 \le i \ne i' \le m-2\) then \(c_\Pi(u) \ne c_\Pi(v)\) since \(d(u, C_{\sum_{z=1}^r n_z + 2}) \ne d(v, C_{\sum_{z=1}^r n_z + 2})\).

The color codes of vertices are all distinct and so c is a locating coloring of \(D_m(K_{n_1,n_2,\ldots,n_r})\). Hence \(\chi_L(D_m(K_{n_1,n_2,\ldots,n_r})) = \sum_{z=1}^r n_z + 2\).

Lemma 3.5. Let \(m \ge 5\) and \(2 \le n_1 \le n_2\). Then \(\chi_L(D_m(K_{n_1,n_2})) \le n_1 + n_2 + 3\).

Proof. Define a coloring \(c: V(D_m(K_{n_1,n_2})) \to \{1,2,\ldots,n_1+n_2+3\}\) in the following way.

\[c(v_{i,k}^1) = k \quad \text{for } i = 1, 2, \dots, m \text{ and } k = 1, 2, \dots, n_1, \text{ where } (i, k) \neq (1, n_1) \text{ or } (m, n_1),\] \[c(v_{i,k}^2) = n_1 + k \quad \text{for } i = 1, 2, \dots, m \text{ and } k = 1, 2, \dots, n_2, \text{ where } (i, k) \neq (3, n_2) \text{ or } (m, n_2),\] \[c(v_{1,n_1}^1) = n_1 + n_2 + 1,\] \[c(v_{3,n_2}^2) = n_1 + n_2 + 2,\] \[c(v_{m,n_1}^1) = n_1 + n_2 + 3 \quad \text{if } m \text{ is odd},\] \[c(v_{m,n_1}^1) = n_1 \quad \text{if } m \text{ is even},\] \[c(v_{m,n_2}^2) = n_2 \quad \text{if } m \text{ is odd},\] \[c(v_{m,n_2}^2) = n_1 + n_2 + 3 \quad \text{if } m \text{ is even}.\]

Let u and v be any two vertices of \(D_m(K_{n_1,n_2})\) such that u and v belong to the same color class. Consider the following cases.

• If \(u = v_{i,k}^j\) and \(v = v_{i',k}^j\) for \(1 \le i \ne i' \le m, 1 \le j \le 2\) and \(1 \le k \le n_j, |i i'| \ge 2\), then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1 + n_2 + 3}) \ne d(v, C_{n_1 + n_2 + 3})\).
• If \(u = v_{1,k}^1\) and \(v = v_{2,k}^1\) for \(1 \le k \le n_1 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1 + n_2 + 2}) \ne d(v, C_{n_1 + n_2 + 2})\).
• If \(u = v_{i,k}^1\) and \(v = v_{i+1,k}^1\) for odd \(i, 2 \le i \le m-2\), and \(1 \le k \le n_1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+1}) \ne d(v, C_{n_1+n_2+1})\).
• If \(u = v_{i,k}^1\) and \(v = v_{i+1,k}^1\) for even \(i, 2 \le i \le m-2\), and \(1 \le k \le n_1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+3}) \ne d(v, C_{n_1+n_2+3})\).
• If \(u = v_{m-1,k}^1\) and \(v = v_{m,k}^1\) for \(1 \le k \le n_1 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+2}) \ne d(v, C_{n_1+n_2+2})\) if m is odd and \(d(u, C_{n_1+n_2+1}) \ne d(v, C_{n_1+n_2+1})\) if m is even.
• If \(u = v_{m-1,n_1}^1\) and \(v = v_{m,n_1}^1\) for even m then \(c_{\Pi}(u) \neq c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+1}) \neq d(v, C_{n_1+n_2+1})\).
• If \(u=v_{1,k}^2\) and \(v=v_{2,k}^2\) for \(1 \le k \le n_2\) then \(c_\Pi(u) \ne c_\Pi(v)\) since \(d(u,C_{n_1+n_2+3}) \ne d(v,C_{n_1+n_2+3})\).
• If \(u = v_{2,k}^2\) and \(v = v_{3,k}^2\) for \(1 \le k \le n_2 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1 + n_2 + 1}) \ne d(v, C_{n_1 + n_2 + 1})\).
• If \(u = v_{3,k}^2\) and \(v = v_{4,k}^2\) for \(1 \le k \le n_2 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+3}) \ne d(v, C_{n_1+n_2+3})\).

• If \(u = v_{i,k}^2\) and \(v = v_{i+1,k}^2\) for odd \(i, 4 \le i \le m-2\), and \(1 \le k \le n_2\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+3}) \ne d(v, C_{n_1+n_2+3})\).
• If \(u = v_{i,k}^2\) and \(v = v_{i+1,k}^2\) for even \(i, 4 \le i \le m-2\), and \(1 \le k \le n_2\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+1}) \ne d(v, C_{n_1+n_2+1})\).
• If \(u = v_{m-1,k}^2\) and \(v = v_{m,k}^2\) for \(1 \le k \le n_2 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1+n_2+1}) \ne d(v, C_{n_1+n_2+1})\) if m is odd and \(d(u, C_{n_1+n_2+2}) \ne d(v, C_{n_1+n_2+2})\) if m is even.
• If \(u=v_{m-1,n_2}^2\) and \(v=v_{m,n_2}^2\) for odd m then \(c_\Pi(u)\neq c_\Pi(v)\) since \(d(u,C_{n_1+n_2+1})\neq d(v,C_{n_1+n_2+1})\).

Thus distinct vertices have distinct color codes. Hence c is a locating coloring of \(D_m(K_{n_1,n_2})\). \(\square\)

Lemma 3.6. Let \[m \geq 5\], \(r \geq 3\) and \(2 \leq n_1 \leq n_2 \leq \cdots \leq n_r\). Then \(\chi_L(D_m(K_{n_1,n_2,...,n_r})) = \sum_{z=1}^r n_z + 2\).

Proof. According to Lemma 3.1, it suffices to construct an optimal locating \((\sum_{z=1}^r n_z + 2)\)-coloring of \(D_m(K_{n_1,n_2,\dots,n_r})\). Let us define a coloring \(c:V(D_m(K_{n_1,n_2,\dots,n_r})) \to \{1,2,\dots,\sum_{z=1}^r n_z + 2\}\) in the following way. Let \(c(v_{m,n_1}^1) = \sum_{z=1}^r n_z + 2\) and for \(i=2,3,\dots,m-1\), let \(c(v_{i,n_1}^1) = \sum_{z=1}^r n_z + 1\). Next, let \(c(v_{i,k}^j) = \sum_{z=1}^{j-1} n_z + k\) for \(i=1,2,\dots,m,\ j=1,2,\dots,r\) and \(k=1,2,\dots,n_j\), where \((i,k) \neq (2,n_1),(3,n_1),\dots,(m,n_1)\).

We show that the color codes for each vertex are distinct. Let us consider any two distinct vertices \(u, v \in V(D_m(K_{n_1,n_2,...,n_r}))\) such that u and v belong to the same color class. Consider the following cases.

• If \(u = v_{i,k}^1\) and \(v = v_{i',k}^1\) for \(1 \le i \ne i' \le m-2\) and \(1 \le k \le n_1-1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{\sum_{z=1}^r n_z+2}) \ne d(v, C_{\sum_{z=1}^r n_z+2})\).
• If \(u = v_{i,k}^1\) and \(v = v_{i',k}^1\) for \(1 \le i \le m-2\), \(m-1 \le i' \le m\), \(1 \le k \le n_1-1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1}) \ne d(v, C_{n_1})\).
• If \(u = v_{m-1,k}^1\) and \(v = v_{m,k}^1\) for \(1 \le k \le n_1 1\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1}) \ne d(v, C_{n_1})\).
• If \(u=v_{i,n_1}^1\) and \(v=v_{i',n_1}^1\) for \(2 \leq i \neq i' \leq m-2\) then \(c_\Pi(u) \neq c_\Pi(v)\) since \(d(u,C_{\sum_{z=1}^r n_z+2}) \neq d(v,C_{\sum_{z=1}^r n_z+2})\).
• If \(u = v_{i,n_1}^1\) and \(v = v_{m-1,n_1}^1\) for \(1 \le i \le m-2\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u,C_{n_1}) \ne d(v,C_{n_1})\).
• If \(u = v_{i,k}^j\) and \(v = v_{i',k}^j\) for \(1 \le i \ne i' \le m-1\), \(2 \le j \le r\) and \(1 \le k \le n_j\) then \(c_\Pi(u) \ne c_\Pi(v)\) since \(d(u, C_{\sum_{z=1}^r n_z + 2}) \ne d(v, C_{\sum_{z=1}^r n_z + 2})\).
• If \(u = v_{i,k}^j\) and \(v = v_{m,k}^j\) for \(1 \le i \le m-1\), \(2 \le j \le r\) and \(1 \le k \le n_j\) then \(c_{\Pi}(u) \ne c_{\Pi}(v)\) since \(d(u, C_{n_1}) \ne d(v, C_{n_1})\).

The locating chromatic number for m-shadow of a connected graph | I Wayan Sudarsana et al.

The color codes of vertices are all distinct. So \[\chi_L(D_m(K_{n_1,n_2,\dots,n_r})) = \sum_{z=1}^r n_z + 2.\]

Summarizing the results from (3) and Lemmas 3.1, 3.2, 3.3, 3.4, 3.5 and 3.6 we have the following theorem which gives the locating chromatic number for m-shadow of complete multipartite graphs.

Theorem 3.1. Let m > 2, r > 2 and \(1 < n_1 < n_2 < \cdots < n_r\). Then

\[\chi_L(D_m(K_{n_1,n_2,\dots,n_r})) = \begin{cases} 2\sum_{z=1}^r n_z, & \text{if } m=2, \ r\geq 2 \text{ and } 1\leq n_1 \leq n_2 \leq \dots \leq n_r, \\ \sum_{z=1}^r n_z + 2, & \text{if } m\geq 3, \ r\geq 2 \text{ and } 1=n_1 \leq n_2 \leq \dots \leq n_r \text{ or } m\geq 5, \ r\geq 3 \text{ and } 2\leq n_1 \leq n_2 \leq \dots \leq n_r. \end{cases}\]

Moreover, \[\sum_{z=1}^{r} n_z + 2 \le \chi_L(D_m(K_{n_1,n_2,...,n_r})) \le \sum_{z=1}^{r} n_z + 3\] if \(3 \le m \le 4\), \(r \ge 2\) and \(2 \le n_1 \le n_2 \le \cdots \le n_r\) or \(m \ge 5\), \(r = 2\) and \(2 \le n_1 \le n_2\).

The next two corollaries presenting the locating chromatic number for m-shadow of stars and complete graphs follow from Theorem 3.1.

Corollary 3.1. Let \(m \ge 3\) and \(n \ge 1\). Then \(\chi_L(D_m(K_{1,n})) = n + 3\).

Corollary 3.2. Let \(m \geq 3\) and \(n \geq 2\). Then \(\chi_L(D_m(K_n)) = n + 2\).

4. The m-shadow of paths

Let \(G \cong D_m(P_n)\) be the m-shadow of a path with vertex set \(V(G) = \bigcup_{i=1}^m V(P_n^i)\), where \(V(P_n^i) = \{v_i^j : j = 1, 2, \dots, n\}\) is the vertex subset in the ith copy of \(P_n\), \(i = 1, 2, \dots, m\).

In [13], Behtoei and Omoomi proved that \(\chi_L(P_m \times P_n) = 4\) for \(n \ge m \ge 2\). In fact, we have \(D_m(P_2) \cong P_m \times P_2\) for \(m \ge 2\). So

\[\chi_L(D_m(P_2)) = 4. (4)\]

For \(m \geq 3\) and n = 3 we obtain \(D_m(P_3) \cong D_m(K_{1,2})\), and for m = 2 and n = 3 we get \(D_2(P_3) \cong D_2(K_{1,2})\). So from Corollary 3.1 and (3),

\[\chi_L(D_m(P_3)) = 5 \tag{5}\]

and

\[\chi_L(D_2(P_3)) = 6, (6)\]

respectively.

In [15], it was proved that \(\chi_L(P_n) = 3\) for \(n \geq 3\).

Lemma 4.1. Let \(m \geq 3\). Then \(\chi_L(D_m(P_4)) = 4\).

Proof. By Theorem 2.1, \(\chi_L(D_m(P_4)) \ge 4\). Define a vertex 4-coloring c of \(D_m(P_4)\) in the following way.

\[\begin{split} c(v_i^j) &= 1 & \text{for } i = 1, 2, \dots, m-2 \text{ and } j = 1, 4, \\ c(v_i^j) &= 2 & \text{for } i = 1, 2, \dots, m \text{ and } j = 3 \text{ or } i = m-1 \text{ and } j = 1, \\ c(v_i^j) &= 3 & \text{for } i = m \text{ and } j = 1, 4, \\ c(v_i^j) &= 4 & \text{for } i = 1, 2, \dots, m \text{ and } j = 2 \text{ or } i = m-1 \text{ and } j = 4. \end{split}\]

Then we obtain the color codes of vertices below.

\[\begin{split} c_{\Pi}(v_i^1) &= (0,2,m-i,1) & \text{for } i=1,2,\dots,m-2, \\ c_{\Pi}(v_{m-1}^1) &= (2,0,2,1), \\ c_{\Pi}(v_m^1) &= (2,2,0,1), \\ c_{\Pi}(v_i^2) &= (1,1,m-i,0) & \text{for } i=1,2,\dots,m-1, \\ c_{\Pi}(v_m^2) &= (2,1,1,0), \\ c_{\Pi}(v_i^3) &= (1,0,m-i,1) & \text{for } i=1,2,\dots,m-1, \\ c_{\Pi}(v_m^3) &= (2,0,1,1), & \text{for } i=1,2,\dots,m-2, \\ c_{\Pi}(v_{m-1}^4) &= (0,1,m-i,2) & \text{for } i=1,2,\dots,m-2, \\ c_{\Pi}(v_{m-1}^4) &= (2,1,2,0), \\ c_{\Pi}(v_m^4) &= (2,1,0,2). \end{split}\]

Clearly the color codes are distinct for all vertices. So \(\chi_L(D_m(P_4))=4\) and the proof is completed.

Lemma 4.2. Let \(n \ge 4\). Then \(\chi_L(D_2(P_n)) = 5\).

Proof. We have \(\chi_L(D_2(P_n)) \geq 4\) according to Theorem 2.1. Assume now, \(\chi_L(D_2(P_n)) = 4\). Let c' be a locating 4-coloring of \(D_2(P_n)\). We may assume, without loss of generality, that \(\{c'(v_1^1),c'(v_2^1)\}=\{1,2\}\) and \(\{c'(v_1^2),c'(v_2^2)\}=\{3,4\}\). Then \(\{c'(v_1^j),c'(v_2^j):j\neq 1 \text{ is odd and } c'(v_1^j)\neq c'(v_2^j)\}=\{1,2\}\) and \(\{c'(v_1^j),c'(v_2^j):j\neq 2 \text{ is even and } c'(v_1^j)\neq c'(v_2^j)\}=\{3,4\}\). It is easy to see that the color codes of vertices are not unique. So \(\chi_L(D_2(P_n))\geq 5\).

Let c be a vertex 5-coloring of \(D_2(P_n)\) defined such that

\[c(v_1^j)=1 \qquad \qquad \text{if $n$ is odd, for $j=1,3,\ldots,n$ or } \\ n \text{ is even, for $j=2,4,\ldots,n$,} \\ c(v_i^j)=2 \qquad \qquad \text{if $n$ is odd, for $i=1$ and $j=4,6,\ldots,n-1$ or } \\ n \text{ is odd, for $i=2$ and $j=2$ or } \\ n \text{ is even, for $i=1$ and $j=3,5,\ldots,n-1$ or } \\ n \text{ is even, for $i=2$ and $j=1$,} \\ c(v_i^j)=3 \qquad \qquad \text{if $n$ is odd, for $i=1$ and $j=2$ or } \\ n \text{ is odd, for $i=2$ and $j=5,7,\ldots,n$ or } \\ n \text{ is even, for $i=1$ and $j=1$ or } \\ n \text{ is even, for $i=2$ and $j=4,6,\ldots,n$,} \\ c(v_2^j)=4 \qquad \qquad \text{if $n$ is odd, for $j=1,4,6,\ldots,n-1$ or } \\ n \text{ is even, for $j=3,5,\ldots,n-1$,} \\ c(v_2^j)=5 \qquad \qquad \text{if $n$ is odd, for $j=3$ or } \\ n \text{ is even, for $j=2$.} \\\]

We show that the color codes for all vertices of \(D_m(P_n)\) are distinct. Let us divide the cases depending on the parity of n. First let \(n \geq 5\) be odd. We have the color codes as follows. \(c_\Pi(v_1^1) = (0,1,1,2,2), \ c_\Pi(v_2^1) = (2,1,1,0,2), \ c_\Pi(v_1^2) = (1,2,0,1,1), \ c_\Pi(v_2^2) = (1,0,2,1,1), \ c_\Pi(v_1^3) = (0,1,1,1,2)\) and \(c_\Pi(v_2^3) = (2,1,1,1,0)\). For odd \(j \geq 5\) we obtain \(c_\Pi(v_1^j) = (0,1,2,1,j-3)\) and \(c_\Pi(v_2^j) = (2,1,0,1,j-3)\). For even \(j \geq 4\) we obtain \(c_\Pi(v_1^j) = (1,0,1,2,j-3)\) and \(c_\Pi(v_2^j) = (1,2,1,0,j-3)\).

Now let \(n \geq 4\) be even. Then we get the color codes as follows. \(c_{\Pi}(v_1^1) = (1, 2, 0, 2, 1)\), \(c_{\Pi}(v_2^1) = (1, 0, 2, 2, 1)\), \(c_{\Pi}(v_1^2) = (0, 1, 1, 1, 2)\) and \(c_{\Pi}(v_2^2) = (2, 1, 1, 1, 0)\). For odd \(j \geq 3\) we have \(c_{\Pi}(v_1^j) = (1, 0, 1, 2, j - 2)\) and \(c_{\Pi}(v_2^j) = (1, 2, 1, 0, j - 2)\). For even \(j \geq 4\) we have \(c_{\Pi}(v_1^j) = (0, 1, 2, 1, j - 2)\) and \(c_{\Pi}(v_2^j) = (2, 1, 0, 1, j - 2)\).

Since the color codes are distinct for all cases, c is a locating coloring of \(D_m(P_n)\). Hence \(\chi_L(D_m(P_n))=5\).

Lemma 4.3. Let \(m \geq 3\) and \(n \geq 5\). Then \(\chi_L(D_m(P_n)) \leq 5\).

Proof. Define a coloring \(c: V(D_m(P_n)) \to \{1, 2, \dots, 5\}\) as follows.

\[\begin{split} c(v_i^1) &= 1 & \text{for } i = 1, 2, \dots, m, \\ c(v_i^j) &= 2 & \text{for } i = 1, 2, \dots, m \text{ and odd } j \neq 1, \\ c(v_i^j) &= 3 & \text{for } i = 1, 2, \dots, m - 2 \text{ and even } j, \\ c(v_{m-1}^j) &= 4 & \text{for even } j, \\ c(v_m^j) &= 5 & \text{for even } j. \end{split}\]

Under the coloring c, we obtain the color codes of vertices as follows.

\[\begin{split} c_\Pi(v_m^1) &= (0,2,3,1,1),\\ c_\Pi(v_{m-i}^1) &= (0,2,1,i,i) & \text{for odd } i,\\ c_\Pi(v_{m-i}^1) &= (0,2,1,i-1,i+1) & \text{for even } i,\\ c_\Pi(v_m^j) &= (j-1,0,3,1,1) & \text{for odd } j \neq 1,\\ c_\Pi(v_{m-i}^j) &= (j-1,0,1,i,i) & \text{for odd } i \text{ and odd } j \neq 1,\\ c_\Pi(v_{m-i}^j) &= (j-1,0,1,i-1,i+1) & \text{for even } i \text{ and odd } j \neq 1,\\ c_\Pi(v_{m-i}^j) &= (j-1,1,0,i-1,i+1) & \text{for odd } i \neq 1 \text{ and even } j,\\ c_\Pi(v_{m-i}^j) &= (j-1,1,0,i,i) & \text{for even } i \text{ and even } j,\\ c_\Pi(v_{m-1}^j) &= (j-1,1,2,0,2) & \text{for even } j,\\ c_\Pi(v_m^j) &= (j-1,1,2,2,0) & \text{for even } j. \end{split}\]

It is easy to see that distinct vertices have distinct color codes. Thus χL(Dm(Pn)) ≤ 5.

Immediately from Theorem 2.1, (4), (5), (6), and Lemmas 4.1, 4.2 and 4.3, we obtain the following theorem giving the locating chromatic number for m-shadow of paths.

Theorem 4.1. Let m ≥ 2 and n ≥ 2. Then

\[\chi_L(D_m(P_n)) = \begin{cases} 4, & \text{if } m \ge 2 \text{ and } n = 2 \text{ or } m \ge 3 \text{ and } n = 4, \\ 5, & \text{if } m = 2 \text{ and } n \ge 4 \text{ or } m \ge 3 \text{ and } n = 3, \\ 6, & \text{if } m = 2 \text{ and } n = 3. \end{cases}\]

Moreover, 4 ≤ χL(Dm(Pn)) ≤ 5 if m ≥ 3 and n ≥ 5.

5. Remark and Conclusion

Here, we state the new result corresponding to the tight lower bound and upper bound of locating chromatic number on m-shadow of a graph G, that is χL(G) + 1 ≤ χL(Dm(G)) ≤ 2χL(G). Moreover, we also obtain the exact value of χL(Dm(G)), when G is a path or a complete multipartite graph on some particular orders. In future, we need to classify the families of graphs in which the lower or upper bound holds.

Acknowledgement

The first author gratefully acknowledges to Kemendikbud-Ristek on Matching Fund Program for financial support under grant number: 472/E1/KS.06.02/2022.

References

• [1] I.H. Agustin, F. Susanto, Dafik, R.M. Prihandini, R. Alfarisi, and I W. Sudarsana, On Hsupermagic labelings of m-shadow of paths and cycles, Int. J. Math. Math. Sci. 2019 (2019), Article ID 8780329.
• [2] Arfin and E.T. Baskoro, Unicyclic graph of order n with locating-chromatic number n − 2, Jurnal Matematika dan Sains 24 (2019), 36–45.
• [3] Asmiati, H. Assiyatun, and E.T. Baskoro, Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43A (2010), 1–8.
• [4] Asmiati, E.T. Baskoro, H. Assiyatun, D. Suprijanto, R. Simanjuntak, and S. Uttunggadewa, The locating-chromatic number of firecracker graphs, Far East Journal of Mathematical Sciences 63 (2012), 11–23.
• [5] Asmiati, I.K.S.G. Yana, and L. Yulianti, On the locating chromatic number of certain barbell graphs, Int. J. Math. Math. Sci. 2018 (2018), Article ID 5327504.
• [6] H. Assiyatun, D.K. Syofyan, and E.T. Baskoro, Calculating an upper bound of the locatingchromatic number of trees, Theoret. Comput. Sci. 806 (2020), 305–309.
• [7] E.T. Baskoro and Arfin, All unicyclic graphs of order n with locating-chromatic number n−3, Indonesian Journal of Combinatorics 5 (2021), 73–81.
• [8] E.T. Baskoro and Asmiati, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1 (2013), 109–117.
• [9] E.T. Baskoro and D.I.D. Primaskun, Improved algorithm for the locating chromatic number of trees, Theoret. Comput. Sci. 856 (2021), 165–168.
• [10] E.T. Baskoro and I.A. Purwasih, The locating-chromatic number for corona product of graphs, Southeast Asian Journal of Sciences 1 (2012), 126–136.
• [11] A. Behtoei and M. Anbarloei, The locating chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014), 1491–1504.
• [12] A. Behtoei and B. Omoomi, On the locating chromatic number of kneser graphs, Discrete Appl. Math. 159 (2011), 2214–2221.
• [13] A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs, Ars Combin. 126 (2016), 221–235.
• [14] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, Graphs of order n with locating-chromatic number n − 1, Discrete Math. 269 (2003), 65–79.
• [15] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, The locating chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89–101.

• [16] M. Furuya and N. Matsumoto, Upper bounds on the locating chromatic number of trees, Discrete Appl. Math. 257 (2019), 338–341.
• [17] M. Ghanem, H. Al-Ezeh, and A. Dabbour, Locating chromatic number of powers of paths and cycles, Symmetry 11 (2019), 389.
• [18] Y. Hafidh and E.T. Baskoro, On the locating chromatic number of trees, Int. J. Math. Comput. Sci. 17 (2022), 377–394.
• [19] N. Inayah, W. Aribowo, and M.M.W. Yahya, The locating chromatic number of book graph, J. Math. 2021 (2021), Article ID 3716361.
• [20] A. Irawan, Asmiati, L. Zakaria, and K. Muludi, The locating-chromatic number of origami graphs, Algorithms 14 (2021), 167.
• [21] R. Sakri and M. Abbas, On locating chromatic number of moobius ladder graphs, ¨ Proyecciones 40 (2021), 659–669.
• [22] D.K. Syofyan, E.T. Baskoro, and H. Assiyatun, Trees with certain locating-chromatic number, J. Math. Fund. Sci. 48 (2016), 39–47.