On Locating-chromatic Number for Graphs with Dominant Vertices

详细信息    查看全文

• 作者：Des Welyyanti ; ¹ ; ^{deswelyyanti@students.itb.ac.id" class="auth_mail" title="E-mail the corresponding author} ; Edy Tri Baskoro ; Rinovia Simanjuntak ; Saladin Uttunggadewa
• 关键词：locating-chromatic number ; dominant vertex ; coloring ; color.
• 刊名：Procedia Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：74
• 期：Complete
• 页码：89-92
• 全文大小：246 K

文摘

Let c be a k-coloring of a (not necessary connected) graph H. Let П= {C1, C2, · · ·, Ck } be the partition of V(H) induced by c, where Ci is partition class receiving color i. The color code c_П(v) of a vertex v ∈ H is the ordered k-tuple (d(v, C1), d(v, C2), · · ·, d(v, Ck )), where d(v, Ci) = min{d(v, x)|x ∈ Ci} for all i ∈ [1,k]. If all vertices of H have distinct color codes, then c is called a locating k-coloring of H. The locating-chromatic number of H, denoted by χ_L’ (H), is the smallest k such that H admits a locating- coloring with k colors. If there is no integer k satisfying the above conditions, then we say that χ’_L (H) = ∞. Note that if H is a connected graph, then χ_L’ (H) = χL(H). In this paper, we provide upper bounds for the locating-chromatic numbers of connectedgraphs obtained from disconnected graphs where each component contains a single dominant vertex.