×

On labeling the vertices of products of complete graphs with distance constraints. (English) Zbl 1066.05126

Summary: Variations of Hale’s channel assignment problem, the \(L(j, k)\)-labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph \(G\) subject to various distance constraints. The \(\lambda_{j,k}\)-number of \(G\) and the radio number of \(G\) are, respectively the minimum span among all \(L(j, k)\)-labelings, and the minimum span plus 1 of all radio labelings of \(G\) (defined in the introduction). In this paper, we establish the \(\lambda_{j,k}\)-number of \(\prod^q_{i=1} K_{t_i}\) for pairwise relatively prime integers \(t_1< t_2<\cdots< t_q\), \(t_1\geq 2\). We also show the existence of an infinite class of graphs \(G\) with radio number \(|V(G)|\) for any diameter \(d(G)\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chang, SIAM J Discrete Math 9 pp 309– (1996)
[2] Chartrand, Bull Inst Combinat Appl 33 pp 77– (2001)
[3] and A graph labeling problem suggested by FM channel restrictions, preprint. · Zbl 1066.05125
[4] Georges, J Graph Theory 22 pp 47– (1996)
[5] Georges, Cong Numer 101 pp 33– (1994)
[6] Georges, Cong Numer 140 pp 141– (1999)
[7] Georges, SIAM J Discrete Math 14 pp 28– (2000)
[8] Georges, Discrete Math 135 pp 103– (1994)
[9] Griggs, SIAM J Discrete Math 5 pp 586– (1992)
[10] Hale, Proc IEEE 68 pp 1497– (1980)
[11] Van Den Heuvel, J Graph Theory 29 pp 263– (1998)
[12] Liu, Ars Combinat 47 pp 13– (1997)
[13] T-colorings of graphs: Recent results and open problems, Research Report RRR 7-86, RUTCOR, Rutgers University, New Brunswick, NJ, 1986.
[14] ? From garbage to rainbows: Generalizations of graph colorings and their applications,? Proceedings of the Sixth International Conference on the Theory and Applications of Graphs, and (Editors), Wiley, New York, 1989, pp. 1031-1052. · Zbl 0841.05033
[15] Sakai, SIAM J Discrete Math 7 pp 133– (1994)
[16] Whittlesey, SIAM J Discrete Math 8 pp 499– (1995)
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.