A channel assignment problem for optical networks modelled by Cayley graphs

✍ Scribed by Sanming Zhou

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 239 KB
• Volume: 310
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00394-3

✦ Synopsis

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.