The locating chromatic number for m-shadow of a connected graph

Abstract

Let c : V(G)→{1, 2, …, k} be a proper k-coloring of a simple connected graph G. Let Π = {C₁, C₂, …, C_k} be a partition of V(G), where C_i 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, C₂),d(v, C₂),…,d(v, C_k)), where d(v, C_i)=min{d(v, x):x ∈ C_i} 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 D_m(G), is a graph obtained by taking m copies of G, say G₁, G₂, …, G_m, and each vertex v in G_i, i = 1, 2, …, m − 1, is joined to the neighbors of its corresponding vertex v′ in G_i + 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 D_m(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.