The locating chromatic number of the join of graphs

Document Type: Research Paper

Author

Isfahan university of techmology

Abstract

‎Let $f$ be a proper $k$-coloring of a connected graph $G$ and‎
‎$Pi=(V_1,V_2,ldots,V_k)$ be an ordered partition of $V(G)$ into‎
‎the resulting color classes‎. ‎For a vertex $v$ of $G$‎, ‎the color‎
‎code of $v$ with respect to $Pi$ is defined to be the ordered‎
‎$k$-tuple $c_{{}_Pi}(v)=(d(v,V_1),d(v,V_2),ldots,d(v,V_k))$‎,
‎where $d(v,V_i)=min{d(v,x):~xin V_i}‎, ‎1leq ileq k$‎. ‎If‎
‎distinct vertices have distinct color codes‎, ‎then $f$ is called a‎
‎locating coloring‎. ‎The minimum number of colors needed in a‎
‎locating coloring of $G$ is the locating chromatic number of $G$‎,
‎denoted by $Cchi_{{}_L}(G)$‎. ‎In this paper‎, ‎we study the locating chromatic number of the join of graphs‎. ‎We show that when $G_1$ and $G_2$ are two connected graphs with diameter at most two‎, ‎then $Cchi_{{}_L}(G_1vee G_2)=Cchi_{{}_L}(G_1)+Cchi_{{}_L}(G_2)$‎, ‎where $G_1vee G_2$ is the join of $G_1$ and $G_2$‎. ‎Also‎, ‎we determine the‎
‎locating chromatic number of the join of paths‎, ‎cycles and complete multipartite graphs‎.

Keywords

Main Subjects



Volume 40, Issue 6
November and December 2014
Pages 1491-1504
  • Receive Date: 04 May 2012
  • Revise Date: 17 October 2013
  • Accept Date: 05 November 2013