• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Bounds on Directed star arboricity in some digraph classes

Electronic Notes in Discrete Mathematics. 2017. Vol. 62. P. 267-272.
Perret du Cray H., Baïou M., Beaudou L., Limouzy V.

A galaxy is a forest of directed stars. The notion of galaxy can be related to Facility Location problems as well as wavelength assignment problems in optical networks. Amini et al. [Combinatorics, Probability & Computing, 19(2):161–182, 2010.] and Gonçalves et al. [Discrete Applied Mathematics, 160(6):744–754, 2012.] gave bounds on the minimum number of galaxies needed to cover the arcs of a digraph D, called directed star arboricity (dst(D)). They conjectured that those bounds could be improved such that , for and for . In this work, we study the directed star arboricity in two non-trivial digraph classes: k-degenerate digraphs and tournaments.