On the \(L(p,1)\)-labelling of graphs. (English) Zbl 1135.05065
Summary: The \(L(p,q)\)-labelling of graphs, is a graph theoretic framework introduced by J. R. Griggs and R. K. Yeh [SIAM J. Discrete Math. 5, No. 4, 586–595 (1992; Zbl 0767.05080)] to model the channel assignment problem. In this paper we improve the best known upper bound for the \(L(p,1)\)-labelling of graphs with given maximum degree. We show that for any integer \(p \geq 2\), any graph \(G\) with maximum degree \(\Delta \) admits an \(L(p,1)\)-labelling such that the labels range from 0 to \(\Delta ^{2}+(p-1)\Delta -2\).
MSC:
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 0767.05080References:
| [1] | P. Bella, D. Král, B. Mohar, K. Quittnerová, Labeling planar graphs with a condition at distance two, Discrete Math. Theor. Comput. Sci. AE (2005), 41-44.; P. Bella, D. Král, B. Mohar, K. Quittnerová, Labeling planar graphs with a condition at distance two, Discrete Math. Theor. Comput. Sci. AE (2005), 41-44. · Zbl 1192.05131 |
| [2] | Chang, G. J.; Kuo, D., The L(2,1)-labeling problem on graphs, SIAM J. Discrete Math., 9, 309-316 (1996) · Zbl 0860.05064 |
| [3] | Chang, G. J.; Ke, W.-T.; Kuo, D.; Liu, D. D.-F.; Yeh, R. K., On L \((d, 1)\)-labelings of graphs, Discrete Math., 220, 57-66 (2002) · Zbl 0954.05041 |
| [4] | G. Fertin, A. Raspaud, L(p,q) Labeling of \(d\)-dimensional girds, Discrete Math. 307 (16) (2007) 2132-2140.; G. Fertin, A. Raspaud, L(p,q) Labeling of \(d\)-dimensional girds, Discrete Math. 307 (16) (2007) 2132-2140. · Zbl 1119.05096 |
| [5] | Fiala, J.; Fishkin, A. V.; Fomin, F. V., On distance constrained labeling of disk graphs, Theoret. Comput. Sci., 326, 261-292 (2004) · Zbl 1071.68083 |
| [6] | Griggs, J. R.; Yeh, R. K., Labelling graphs with a condition at distance 2, SIAM J. Discrete Math., 5, 586-595 (1992) · Zbl 0767.05080 |
| [7] | van den Heuvel, J.; McGuinness, S., Coloring the square of a planar graph, J. Graph Theory, 42, 2, 110-124 (2003) · Zbl 1008.05065 |
| [8] | J.-H Kang, L(2,1)-labelling of 3-regular Hamiltonian cubic graphs, preprint.; J.-H Kang, L(2,1)-labelling of 3-regular Hamiltonian cubic graphs, preprint. |
| [9] | Král, D., Coloring powers of chordal graphs, SIAM J. Discrete Math., 18, 3, 451-461 (2004) · Zbl 1069.05035 |
| [10] | Král, D.; Škrekovski, R., A theorem about the channel assignment problem, SIAM J. Discrete Math., 16, 3, 426-437 (2003) · Zbl 1029.05053 |
| [11] | McDiarmid, C., On the span in channel assignment problem: bounds, computing and counting, Discrete Math., 266, 387-397 (2003) · Zbl 1014.05024 |
| [12] | M. Molloy, B. Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, vol. 23, Springer, Berlin, 2002.; M. Molloy, B. Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, vol. 23, Springer, Berlin, 2002. · Zbl 0987.05002 |
| [13] | Molloy, M.; Salavatipour, M. R., A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B, 94, 2, 189-213 (2005) · Zbl 1071.05036 |
| [14] | Sakai, D., Labeling chordal graphs: distance two condition, SIAM J. Discrete Math., 7, 133-140 (1994) · Zbl 0794.05118 |
| [15] | Whittlesey, M.; Georges, J.; Mauro, D. W., On the related \(\lambda \)-number of \(Q_n\) and related graphs, SIAM J. Discrete Math., 8, 499-506 (1995) · Zbl 0844.05084 |
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.
