Centre for Discrete and Applicable Mathematics
	CDAM Research Report, LSE-CDAM-96-23 October 1996

Abstract

Vertex-labelling of graphs, where the labels are non-negative integers, provides a natural setting in which to study problems of radio channel assignment. Vertices correspond to transmitter locations, and their labels to radio channels. As a model for the way in which interference is avoided in real radio systems, each pair of vertices has, depending on their separation, a constraint on the difference between the labels that can be assigned. In this paper, we consider the question of finding labellings of minimum span, given a graph and a set of constraints. We focus on the infinite triangular lattice, infinite square lattice and infinite line lattice, and obtain optimal labellings for up to three levels of constraint. We highlight how accepted practice can lead to suboptimal channel assignments and also examine several open questions.

Keywords: graph labelling, radio channel assignment, optimal labelling, graph distance, minimum span

AMS Subject Classifications (1991): 05C78, 05C12, 05C90

If you would like a free copy of this report, please send the number of this report, LSE-CDAM-96-23, together with your name and postal address to:

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-171-955 7732. Fax: +44(0)-171-955 6877. Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html