تعداد نشریات | 5 |
تعداد شمارهها | 108 |
تعداد مقالات | 1,228 |
تعداد مشاهده مقاله | 1,147,080 |
تعداد دریافت فایل اصل مقاله | 1,006,004 |
The locating-chromatic number for Halin graphs | ||
Communications in Combinatorics and Optimization | ||
مقاله 1، دوره 2، شماره 1، شهریور 2017، صفحه 1-9 اصل مقاله (375.71 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2017.13577 | ||
نویسندگان | ||
I.A. Purwasih1؛ Edy T. Baskoro* 1؛ H. Assiyatun1؛ D. Suprijanto1؛ M. Baca2 | ||
1Institut Teknologi Bandung | ||
2Technical University in Koˇsice | ||
چکیده | ||
Let $G$ be a connected graph. Let $f$ be a proper $k$-coloring of $G$ and $\Pi=\{R_1,R_2,\ldots, R_k\}$ be an ordered partition of $V(G)$ into color classes. For any vertex $v$ of $G,$ define the {\em color code} $c_\Pi(v)$ of $v$ with respect to $\Pi$ to be a $k$-tuple $(d(v,R_1),d(v,R_2),\ldots,d(v,R_k)),$ where $d(v,R_i)= \text{min}\{d(v,x)|x\in R_i\}.$ If distinct vertices have distinct color codes, then we call $f$ a {\em locating coloring} of $G.$ The {\em locating-chromatic number} of $G$ is the minimum number $k$ such that $G$ admits a locating coloring with $k$ colors. In this paper, we determine a lower bound of the locating-chromatic number of Halin graphs. We also give the locating-chromatic number of a Halin graph of a double star. | ||
کلیدواژهها | ||
locating-chromatic number؛ Halin؛ double star | ||
مراجع | ||
[1] Asmiati, H. Assiyatun, and E.T. Baskoro, Locating-chromatic number of amalgamation of stars, ITB J. Sci. 43A (2011), no. 1, 1–8.
[2] Asmiati and E.T. Baskoro, Characterizing all graphs containing cycles with locating-chromatic number 3, AIP Conf. Proc. 1450 (2012), 351–357.
[3] Asmiati and E.T. Baskoro, Characterizing all trees with locating-chromatic number 3, Electron. J. Graph Theory Appl. 1 (2013), no. 2, 109–117.
[4] Asmiati, E.T. Baskoro, H. Assiyatun, D. Suprijanto, R. Simanjuntak, and S. Uttunggadewa, The locating-chromatic number of firecracker graphs, Far East J. Math. Sci. 63 (2012), no. 1, 11–23.
[5] C.A. Barefoot, Hamiltonian connectivity of the halin graphs, Congr. Numer. 58 (1987), 93–102.
[6] E.T. Baskoro and I.A. Purwasih, The locating-chromatic number for corona product of graphs, Southeast Asian J. Sci. 1 (2012), no. 1, 126–136.
[7] A. Behtoei and M. Anbarloei, The locating-chromatic number of the join of graphs, Bull. Iranian Math. Soc. 40 (2014), no. 6, 1491–1504.
[8] A. Behtoei and B. Omoomi, On the locating-chromatic number of cartesian product of graphs, Ars. Combin. 126 (2016), 221--235.
[9] G. Chartrand, D. Erwin, M.A. Henning, P.J. Slater, and P. Zhang, The locating-chromatic number of a graph, Bull. Inst. Combin. Appl. 36 (2002), 89–101.
[10] , Graphs of order n with locating-chromatic number n − 1, Discrete Math. 269 (2003), no. 1-3, 65–79.
[11] G. Cornuejols, D. Naddef, and W.R. Pulleyblank, Halin graphs and the travelling salesman problem, Math. Program. 26 (1983), no. 3, 287–294.
[12] R. Halin, Studies on minimally n-connected graphs, Combinatorial Mathematics and its applications (1971), 129–136.
[13] H.-H. Lai, K.-W. Lih, and P.-Y. Tsai, The strong chromatic index of Halin graphs, Discrete Math. 312 (2012), no. 9, 1536–1541. | ||
آمار تعداد مشاهده مقاله: 1,753 تعداد دریافت فایل اصل مقاله: 1,630 |