Optical All-to-All Communication for Some Product Graphs

摘要

The problem of all-to-all communication in a network con-sists of designing directed paths between any ordered pair of vertices in a symmetric directed graph and assigning them minimum number of colours such that every two dipaths sharing an edge have distinct colour. We prove several exact results on the number of colours for some Carte-sian product graphs, including 2-dim.ensional (toroidal) square meshes of odd side, which completes previous results for even sided square meshes.