The locating-chromatic number for Halin graphs

Document Type : Original paper

Authors

1 Institut Teknologi Bandung

2 Technical University in Koˇsice

Abstract

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.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 2, Issue 1
June 2017
Pages 1-9

Files

Share

How to cite

Statistics