×

An asymptotic approach to the channel assignment problem. (English) Zbl 0579.05058

Let \(T\) be a nonempty finite set of positive integers, and let \(G\) be a finite simple graph. A \(T\)-coloring \(f\) of \(G\) is an assignment of an integer \(f(v)\) to each vertex \(v\) of \(G\) such that \(| f(v)-f(w)| \not\in T\cup \{0\}\) whenever \(v\) and \(w\) are adjacent in \(G\). The span of \(f\) is the difference between the largest and smallest integers assigned, and the \(T\)-span of \(G\) is the minimum span over all possible assignments \(f\). (The problem arises from the formulation by W. K. Hale of the channel assignment problem for potentially interfering communication nets.)
Let \(s(T,n)\) denote the \(T\)-span of the complete graph \(K_ n\) on \(n\) vertices. It is shown that there is a “rate function” \(r\) from the set of all finite nonempty sets \(T\) of positive integers to the set of positive rationals not greater than \(1/2\), such that as \(n\to \infty\) have \(\lim (n/s(T,n))=r(T)\). Moreover, a finite algorithm is given for computing \(r(T)\); the algorithm is exponential in the largest element of \(T\), but allows \(K_ n\) to be \(T\)-colored in an “asymptotically optimal” way in constant time (as a function of \(n\)). The output of the algorithm is an infinite sequence of integers (generated from a certain previously computed periodic sequence of zeros and ones), with the property that its first n elements may be used to \(T\)-color \(K_ n\) so that the resulting span differs from \(n/r(T)\) by no more than some fixed integer; this coloring is thus “asymptotically optimal” in the sense that the error \(e(n)\) between its span and \(s(T,n)\) has the property that \(e(n)/n\to 0\) as \(n\to \infty.\)
Some properties of \(r(T)\) are developed, in terms of the structure of the set \(T\). These include general bounds for \(r(T)\), and exact values for certain special sets \(T\).
Reviewer: T. D. Parsons

MSC:

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, Brian; Parsons, T. D., Isomorphism of circulant graphs and digraphs, Discrete Math., 25, 97, (1979) · Zbl 0402.05038 · doi:10.1016/0012-365X(79)90011-6
[2] Cozzens, MargaretB.; Roberts, FredS., {\it T}-colorings of graphs and the channel assignment problem, Congr. Numer., 35, 191, (1982) · Zbl 0537.05023
[3] Golomb, S. W., Shift Register Sequences, (1982)
[4] Hale, W. K., Frequency assignment: theory and applications, Proceedings of the IEEE, 68, 1497, (1980)
[5] Parsons, T. D., Circulant graph imbeddings, J. Combin. Theory Ser. B, 29, 310, (1980) · Zbl 0388.05010 · doi:10.1016/0095-8956(80)90088-X
[6] Pólya, Georg; Szego˝, Gábor, Aufgaben und Lehrsätze aus der Analysis. Band I: Reihen, Integralrechnung, Funktionentheorie, (1970) · Zbl 0201.38102
[7] private communication · Zbl 1207.68077
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.