Department of
Applied
Mathematics

Directed star arboricity

Frederic Havet

Mascotte, CNRS-INRIA-UNSA (Sophia Antipolis, France)

Abstract

The directed star arboricity (dst) of a digraph is the minimum number of star forest needed to cover its arcs. It can also be seen as the minimum number of colours to colour the arcs of the digraph so that two arcs get different colours if they have same head or are consecutives (the head of one is the tail of the other).

Motivated by wavelength assignment for multicast in star networks, we study the directed star arboricity of digraphs in terms of their degree. We prove that every digraph D with maximum indegree k satisfies dst(D)<=2k+1, which is one short of the lower bound 2k. We also show that every digraph with maximum degree at most 3 has dst at most 3 and that every 2-diregular digraph has directed star arboricty at most 4.

This is joint work with O. Amini, F. Huc and S. Thomasse.