UNICYCLIC GRAPH OF ORDER 𝐍 WITH CERTAIN LOCATING-CHROMATIC NUMBER
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 <br /> <br /> c_&am...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/25738 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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 <br />
<br />
c_Π (v)=(d(v,L_1 ),d(v,L_2 ),…,(v,L_k )) <br />
<br />
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. <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≥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 <br />
<br />
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. <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≥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 <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)∈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 <br />
<br />
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. <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≥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 <br />
<br />
|
|---|