Spanning galaxies in digraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

Spanning galaxies in digraphs


A star is an arborescence in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. The directed star arboricity of a digraph D, denoted by dst(D), is the minimum number of galaxies needed to cover A(D). In this paper, we show that dst(D)less-than-or-equals, slantΔ(D)+1 and that if D is acyclic then dst(D)less-than-or-equals, slantΔ(D). These results are proved by considering the existence of spanning galaxies in digraphs. Thus, we study the problem of deciding whether a digraph D has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs.

Dates and versions

lirmm-00433050 , version 1 (18-11-2009)



Daniel Gonçalves, Frédéric Havet, Alexandre Pinlou, Stéphan Thomassé. Spanning galaxies in digraphs. EuroComb: European Conference on Combinatorics, Graph Theory and Applications, Sep 2009, Bordeaux, France. pp.139-143, ⟨10.1016/j.endm.2009.07.023⟩. ⟨lirmm-00433050⟩
183 View
0 Download



Gmail Facebook X LinkedIn More