Graph distance-dependent labeling related to code assignment in computer networks. (English) Zbl 1063.05118
The authors study the code assignment problem in computer networks which is a variation of an interesting graph labeling problem introduced by J. R. Griggs and R. K. Yeh [SIAM J. Discrete Math. 5, 586–595 (1992; Zbl 0767.05080)]. In this connection they investigate labeling for nonnegative integers \(d_1\), \(d_2\) such that \((d_1,d_2)\in \{(0, 1),(1,1),(1,2)\}\). It is stated that an \(L_1(d_1,d_2)\)-labeling of a graph \(G\) is a function \(f: V(G)\to \{0,1,2,\dots\}\) such that \(|f(u)- f(v)|\geq d_i\) whenever the distance between \(u\) and \(v\) is \(i\) apart, \(i\in \{1,2\}\). The number \(\lambda_{d_1,d_2}(G)\) denotes the minimum span of any such labeling of \(G\) and some results about \(\lambda_{d_1,d_2}(G)\) for \((d_1,d_2)\in \{(0,1), (1,1), (1,2)\}\) for some particular graphs are presented here. An upper bound on \(\lambda_{1,2}(G)\) in terms of the maximum degree \(\Delta\) of \(G\) is also given in the form \(\lambda_{1,2}(G)\leq 2\Delta^2-\Delta\).
Reviewer: R. N. Kaul (Delhi)
Citations:
Zbl 0767.05080References:
| [1] | Bertossi, IEEE/ACM Trans Networking 3 pp 441– (1995) |
| [2] | and ?-coloring of graphs, Lecture Notes in Computer Science 1770, Springer-Verlag, Berlin, Heidelberg, 2000, pp. 395-406. · Zbl 0982.05050 |
| [3] | Broadhurst, J Undergraduate Math Appl 21 pp 327– (2000) |
| [4] | Chang, Discrete Math 220 pp 57– (2000) |
| [5] | Chang, SIAM J Discrete Math 9 pp 309– (1996) |
| [6] | Gamst, IEEE Trans Vehicular Technol VT-31 pp 132– (1982) |
| [7] | Georges, Congr Numer 101 pp 33– (1994) |
| [8] | Georges, Congr Numer 109 pp 141– (1995) |
| [9] | Georges, J Graph Theory 22 pp 47– (1996) |
| [10] | Georges, Congr Numer 140 pp 141– (1999) |
| [11] | Georges, Discrete Math 135 pp 103– (1994) |
| [12] | Griggs, SIAM J Discrete Math 5 pp 586– (1992) |
| [13] | Hale, Proc IEEE 68 pp 1497– (1980) |
| [14] | van den Heuvel, J Graph Theory 29 pp 263– (1998) |
| [15] | Jha, Ars Combin 55 pp 81– (2000) |
| [16] | Liu, Ars Combin 47 pp 13– (1997) |
| [17] | Sakai, SIAM J Discrete Math 7 pp 133– (1994) |
| [18] | and Upper and lower bounds of a class of channel assignment problems in cellular networks, Technical Report, Arizona State University, Tempe, 1997. |
| [19] | Whittlesey, SIAM J Discrete Math 8 pp 499– (1995) |
| [20] | Wu, Taiwanese J Math 4 pp 397– (2000) |
| [21] | Labeling Graphs with a Condition at Distance Two, Ph.D. thesis, Department of Mathematics, University of South Carolina, 1990. |
| [22] | Yeh, Taiwanese J Math 4 pp 675– (2000) |
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.
