UNICYCLIC GRAPH OF ORDER 𝐍 WITH CERTAIN LOCATING-CHROMATIC NUMBER

• Main Author: - NIM: 90116003 , ARFIN
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/25738
• Institution: Institut Teknologi Bandung

Let G=(V,E) be a connected graph. Let &#928;={L_1,L_2,…,L_k } be an ordered partition of V(G) into the resulting color classes L_i (1&#8804;i&#8804;k) induced by a coloring c of k colors. The color code c_&#928; (v) of a vertex v in G is defined as <br /> <br /> c_&#928; (v)=(d(v,L_1 ),d(v,L_2 ),…,(v,L_k )) <br /> <br /> where d(v,L_i )=min&#8289;{d(v,x)&#9474;x&#8712;L_i } for 1&#8804;i&#8804;k. If for every distinct vertices u and v in G such that c_&#928; (u)&#8800;c_&#928; (v), then c is called a locating-coloring of G. The locating-chromatic number &#967;_L (G) is the minimum number of the locating-coloring of G. <br /> <br /> <br /> 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. <br /> <br /> <br /> 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&#8805;5 having locating-chromatic number k for k&#8712;{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&#8805;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 <br /> <br /> n>t+3 and 2&#8804;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. <br /> <br /> <br /> 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&#8805;5, &#967;_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 <br /> <br /> 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). <br /> <br /> <br /> 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)&#8712;H. Let v be a vertex, and define G~{v} as a graph obtained by connecting a vertex x&#8712;V(G) to v with an edge xv. If H=G~{v} for every <br /> <br /> G&#8712;G and satisfy both of these following conditions: (1) H&#8713;G; and (2) If there exist w&#8712;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&#8712;E(H), then deg_(C_4 (1,1,0,0) )&#8289;&#12310;(y)&#12311;=3; then H&#8712;H. <br /> <br /> <br /> We also give two other classes in H, those are: (1) graph H=C_3~K_(1,n-4) for <br /> <br /> n&#8805;7 such that xv&#8712;E(H) for a vertex x&#8712;V(C_3 ) dan a vertex v&#8712;V(K_(1,n-4)) with deg_(K_(1,n-4) )&#8289;&#12310;(v)&#12311;=n-4; and (2) graph C_4 (n-4,0,0,0) for n&#8805;7 <br /> <br />