Journées GALET

WDM and Directed Star Arboricity of Digraphs

O. Amini
Projet Mascotte

Abstract:

A k-directed-star-coloring of a digraph D is a coloring of arcs of D such that on each vertex an incoming arc has a color different from all other arcs. In this way arcs having same color form a Galaxy, a union of stars. The directed-star-arboricity of a digraph D, denoted by dst(D), is the minimum integer k for which a k-directed-star-coloring of D exists. (For instance orientations of cycles have dst = 2 apart from directed odd circuits.) This notion was defined by Guiduli and is an analog of the star-arboricity defined by Algor and Alon.

The problem we are interested in is related to WDM (Wavelength Division Multiplexing) in star optical network. We are given a star network in which a center node is connected to a set of nodes V . Each node v sends a set of s(v ) multicasts to the sets of nodes S1 (v ), . . . , Ss(v) (v ). The central node redirects an arriving message toward other vertices on the same frequency. We study the general problem of wavelength assignment in this kind of networks, taking into account the interferences. The case of one multicast reduces to k-directed-star-coloring . If the maximum indegree is bounded by l , we prove that dst is at most 2l + 1. This is almost the best possible value as there exist digraphs with directed-star-arboricity twice the maximum indegree. For orientations of subcubic graphs, we prove dst is at most 3.

In the more general case where each edge of the star network has g fibers and we have several mul- ticasts, we give almost tight bounds for the number of colors.

This is a joint work with F. Huc, F. Havet and S. Thomassé.


Frederic Havet
Last modified: Tue Jun 27 10:20:53 MEST 2006