Locating-Chromatic Number of Amalgamation of Stars

Asmiati¹, H.Assiyatun & E.T. Baskoro

¹Combinatorial Mathematics Research Group
FMIPA ITB
Jl. Ganesa 10 Bandung, Bandung 40132, Indonesia
Email : asmiati308@students.itb.ac.id

Let G be a connected graph and c a proper coloring of G. For i=1,2,…,k define the color class C_i as the set of vertices receiving  color i.  The color code  c_P(v) of a vertex v in G is the ordered k-tuple (d(v,C₁),…,d(v,C_k)) where d(v,C₁) is the distance of v to C_i.  If all distinct vertices of G have distinct color codes, then c is called a locating-coloring of G. The locating-chromatic number of graph G, denoted by c_L(G) is the smallest k such that G has a locating coloring with k colors. In this paper we discuss the locating-chromatic number of  amalgamation of stars S_k,m. S_k,m is obtained from k copies of star K_1,m by identifying a leaf from each star. We also determine a sufficient condition for a connected subgraph HÍ S_k,m satisfying c_L(H) ≤  c_L(S_k,m).

Download Article