UNICYCLIC GRAPH OF ORDER 𝐍 WITH CERTAIN LOCATING-CHROMATIC NUMBER - - NIM: 90116003 , ARFIN
Let G=(V,E) be a connected graph. Let Π={L_1,L_2,Ã‚Â…,L_k } be an ordered partition of V(G) into the resulting color classes L_i (1≤i≤k) induced by a coloring c of k colors. The color code c_Π (v) of a vertex v in G is defined as c_Π (v)=(d(v,L_1 ),d(v,L_2 ),Ã‚Â…,(v,L_k )) where d(v,L_i )=min⁡{d(v,x)│x∈L_i } for 1≤i≤k. If for every distinct vertices u and v in G such that c_Π (u)≠c_Π (v), then c is called a locating-coloring of G. The locating-chromatic number χ_L (G) is the minimum number of the locating-coloring of G. Determining the locating-chromatic number of any graph is an NP-hard problem. This means there is no certain algorihm to determine the locating-chromatic number of an arbitrary graph. Therefore, the study of locating-chromatic number is restricted for certain classes of graphs, or by characterizing graphs with certain locating-chromatic number. For a connected graph G, the locating-chromatic number of some classes of G have been obtained, such as for complete multipartite graph, path P_n, cycle C_n, and double star S_(a,b). Further, K_1 and K_2 are the only graphs with locating-chromatic number 1 and 2, respectively. The existence of tree of order n≥5 having locating-chromatic number k for k∈{3,4,Ã‚Â…,n-2,n} has also been prooved. Some studies also characterize some classes of connected graphs with certain locating-chromatic number, i.e. graphs of order n≥4 with locating-chromatic number n-1, trees with locating-chromatic number 3, and tress of order n with locating-chromatic number t, for any integers n and t, where n>t+3 and 2≤t<n/2. The study of locating-chromatic number has also been obtained from some graph operations, such as join of graphs, Cartesian product, and corona product. This research is focusing on characterizing all classes of unicyclic graph, i.e. graph that contain exactly one cycle. Especially, we characterize all unicyclic graphs of order n with locating-chromatic number n, n-1, n-2, and n-3. For any unicyclic graph G of order n≥5, χ_L (G)=n-2 if and ony if G is a graph isomoprh to one of H_1, H_2, H_3, H_4, H_5, H_6, H_7, C_5, dan C_6. We have also characterized all graphs of order n having locating-chromatic number n and n-1. There are only two unicyclic graphs of order n with locating-chromatic number n, those are C_3 and C_4. Then, there are only two unicyclic graphs of order n with locating-chromatic number n-1, those are C_3 (0,0,1) and C_4 (0,0,0,1). Further, we also give some classes of graphs of order n with locating-chromatic number n-3. Let G be a set of all graphs of prder n with locating-chromatic number n-2, i.e. G={H_1,H_2,H_3,H_4,H_5,H_6,H_7,C_5,C_6 }, and let H be a set of all graphs of order n with locating-chromatic number n-3. It is clear that C_4 (1,1,0,0)∈H. Let v be a vertex, and define G~{v} as a graph obtained by connecting a vertex x∈V(G) to v with an edge xv. If H=G~{v} for every G∈G and satisfy both of these following conditions: (1) H∉G; and (2) If there exist w∈V(H) such that H=C_4 (1,1,0,0)~{w}, and y is a vertex in C_4 (1,1,0,0) such that yw∈E(H), then deg_(C_4 (1,1,0,0) )⁡〖(y)〗=3; then H∈H. We also give two other classes in H, those are: (1) graph H=C_3~K_(1,n-4) for n≥7 such that xv∈E(H) for a vertex x∈V(C_3 ) dan a vertex v∈V(K_(1,n-4)) with deg_(K_(1,n-4) )⁡〖(v)〗=n-4; and (2) graph C_4 (n-4,0,0,0) for n≥7