Department of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia
Abstract:
A problem arising from a recent study of scalability of optical networks seeks to assign channels to the vertices of a network so that vertices distance 2 apart receive distinct channels. In this paper we introduce a general channel assignment scheme for Cayley graphs on abelian groups, and derive upper bounds for the minimum number of channels needed for such graphs. As application we give a systematic way of producing near-optimal channel assignments for connected graphs admitting a vertex-transitive abelian group of automorphisms. Hypercubes are examples of such graphs, and for them our near-optimal upper bound gives rise to the one obtained recently by Wan.