×

Optimal radiocoloring of trees. (English) Zbl 1435.05177

Summary: 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.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W.K. Hale, Frequency assignment: Theory and applications, Proc. IEEE 68 (1980) 1497-1514.
[2] J.R. Griggs, R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595. · Zbl 0767.05080
[3] G.J. Chang, D. Kuo, The L(2; 1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309-316. · Zbl 0860.05064
[4] J.P. Georges, D.W. Mauro, Labeling trees with a condition at distance two, Discrete Math. 269 (2003) 127-148. · Zbl 1035.05078
[5] W.F. Wang, The L(2; 1)-labelling of trees, Discrete Appl. Math. 154 (2007) 598-603. · Zbl 1088.05066
[6] R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217-1231. · Zbl 1094.05047
[7] T. Calamoneri, The L(h; k)-labelling problem: an updated survey and annotated bibliography, Comput. J. 54 (2011) 1344-1371.
[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. · Zbl 1077.68072
[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 · Zbl 0996.68515
[10] Science, Lecture Notes of Computer Science, vol. 1893, pp. 363-372. Springer (2000). · Zbl 0996.68515
[11] J. Griggs, D. Liu, Minimum span channel assignments, Recent Advances in Radio Channel Assignments, Invited Minisymposium, Discrete Math. (1998).
[12] Y.L. Lin, S. Skiena, Algorithms for square roots of graphs, SIAM J. Discrete Math. 8 (1995) 99-118. · Zbl 0821.05052
[13] K.W. Lih, W.F. Wang, Coloring the square of an outerplanar graph, Taiwanese J. Math. 10(4)(2006) 1015-1023. · Zbl 1135.05022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.