پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,792 |
| تعداد مقالات | 14,626 |
| تعداد مشاهده مقاله | 38,947,702 |
| تعداد دریافت فایل اصل مقاله | 15,162,443 |
A bound for the locating chromatic number of trees | ||
| Transactions on Combinatorics | ||
| مقاله 3، دوره 4، شماره 1، خرداد 2015، صفحه 31-41 اصل مقاله (273.56 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2015.6024 | ||
| نویسندگان | ||
| Ali Behtoei* ؛ Mahdi Anbarloei | ||
| Imam Khomeini International University | ||
| چکیده | ||
| 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):~x\in V_i\}, 1\leq i\leq 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 $\chi_{L}(G)$. In this paper, we study the locating chromatic numbers of trees. We provide a counter example to a theorem of Gary Chartrand et al. [G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl., 36 (2002) 89-101] about the locating chromatic number of trees. Also, we offer a new bound for the locating chromatic number of trees. Then, by constructing a special family of trees, we show that this bound is best possible. | ||
| کلیدواژهها | ||
| Locating coloring؛ Locating chromatic number؛ tree؛ maximum degree | ||
| مراجع | ||
|
A. H. Assiyatun and E. T. Baskoro (2011) Locating-chromatic number of amalgamation of stars ITB J. Sci. 43A, 1-8
A. Behtoei and B. Omoomi, On the locating chromatic number of the cartesian product of graphs to appear in Ars
Combin.
A. Behtoei and B. Omoomi (2011) On the locating chromatic number of Kneser graphs Discrete Appl. Math. 159, 2214-2221
G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2002) The locating-chromatic number of a graph Bull. Inst. Combin. Appl. 36, 89-101
G. Chartrand, D. Erwin, M. A. Henning, P. J. Slater and P. Zhang (2003) Graphs of order n with locating-chromatic
number n − 1 Discrete Math. 269 (13), 65-79
G. Chartrand, F. Okamoto and P. Zhang (2009) The metric chromatic number of a graph Australas. J. Combin. 44, 273-286
G. Chartrand, V. Saenpholphat and P. Zhang (2005) Resolving edge colorings in graphs Ars Combin. 74, 33-47
G. Chartrand, E. Salehi and P. Zhang (2000) The partition dimension of a graph, Aequationes Math. 59 (1-2), 45-54
F. Harary and R. A. Melter (1976) On the metric dimension of a graph Ars Combinatoria 2, 191-195
V. Saenpholphat and P. Zhang Conditional resolvability in graphs: A survey 2004 (37-40), 1997-2017
| ||
|
آمار تعداد مشاهده مقاله: 4,323 تعداد دریافت فایل اصل مقاله: 2,954 |
||