Korean J. Math. Vol. 27 No. 4 (2019) pp.831-841
DOI: https://doi.org/10.11568/kjm.2019.27.4.831

Optimal radiocoloring of trees

Article Sidebar

PDF
Published: Dec 30, 2019
Keywords:
radiocoloring, order, span, tree, caterpillar
Mathematics Subject Classification:
05C15

Main Article Content

Xiaoling Zhang
College of Mathematics and Computer Science Quanzhou Normal University Quanzhou 362000, Fujian, P.R. China

Abstract

A Radiocoloring (RC) of a graph $G$ is a function $f$ from the vertex set $V(G)$ to the set of all non-negative integers (labels) such that $|f(u)-f(v)|\geq 2$ if $d(u,v) = 1$ and $|f(u)-f(v)|\geq 1$ if $d(u, v) = 2$. The number of discrete labels and the range of labels used are called order and span, respectively. In this paper, we concentrate on the minimum order span Radiocoloring Problem (RCP) of trees. The optimization version of the minimum order span RCP that tries to find, from all minimum order assignments, one that uses the minimum span. We provide attainable lower and upper bounds for trees. Moreover, a complete characterization of caterpillars (as a subclass of trees) with the minimum order span is given.



Article Details

Supporting Agencies

This research is supported by NSFC No. 11601265 and High-level Talent Innova- tion and Entrepreneurship Project of Quanzhou City China No. 2017Z033.

References

[1] W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE 68 (1980) 1497-1514. Google Scholar

[2] J.R. Griggs, R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595. Google Scholar

[3] G.J. Chang, D. Kuo, The L(2; 1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309-316. Google Scholar

[4] J.P. Georges, D.W. Mauro, Labeling trees with a condition at distance two, Discrete Math. 269 (2003) 127-148. Google Scholar

[5] W.F. Wang, The L(2; 1)-labelling of trees, Discrete Appl. Math. 154 (2007) 598-603. Google Scholar

[6] R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217-1231. Google Scholar

[7] T. Calamoneri, The L(h; k)-labelling problem: an updated survey and annotated bibliography, Comput. J. 54 (2011) 1344-1371. Google Scholar

[8] D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou, P.G. Spirakis, Radiocoloring in planar graphs: Complexity and approximations, Theo. Comput. Sci. 340 (2005) 514-538. Google Scholar

[9] D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou, P.G. Spirakis, NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs, In: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Google Scholar

[10] Science, Lecture Notes of Computer Science, vol. 1893, pp. 363-372. Springer (2000). Google Scholar

[11] J. Griggs, D. Liu, Minimum span channel assignments, Recent Advances in Radio Channel Assignments, Invited Minisymposium, Discrete Math. (1998). Google Scholar

[12] Y.L. Lin, S. Skiena, Algorithms for square roots of graphs, SIAM J. Discrete Math. 8 (1995) 99-118. Google Scholar

[13] K.W. Lih, W.F. Wang, Coloring the square of an outerplanar graph, Taiwanese J. Math. 10(4)(2006) 1015-1023. Google Scholar