The Locating Chromatic Number of Comb Product of Star Graph and Complete Graph
Asmiati and Wenty Okzarima

Department of Mathematics, Universitas Lampung, Lampung-Indonesia, 35145

Abstract

Let -H=(V,E)- be a connected graph, Let -c- be a proper -k--coloring of -H- with color -\{1, 2, . . ., k\}- and - \Pi=\{A_1, A_2, ..., A_k\}- be a partition of -V(H)- which is induced by the coloring -c-. The color code -c_\Pi(w)- of -w- is the ordered -k--tuple -(d(w,A_1), d(w,A_2), ..., d(w,A_k)))- where -d(w,A_i)=- min -\{d(w,x)|x \in A_i\}- for any -i \in \{1,2,3,...,k\} -. If all distinct vertices of -H- have distinct color codes, then -c- is called a -k--locating coloring of -H-. The minimum number of colors used for locating coloring is called the locating chromatic number, denoted by -\chi_L(H)-.

Let -S_n- and -K_n- be star graph and complete graph, respectively. Let -o- be a vertex of -K_n-. The comb product between -S_n- and -K_n-, denoted by -S_n \rhd K_n-, is a graph obtained by taking one copy of -S_n- and -|V(S_n)|- copies of -K_n- and grafting the -i--th copy of -K_n- at the vertex -o- to the -i--th vertex of -S_n-. In this paper, we obtain that -\chi_L(S_n \rhd K_n)=n+1- for -n\geq 3-.

Keywords: locating chromatic number, star graph, complete graph, comb product.

Topic: MATHEMATICS AND STATISTICS