Spanning galaxies in digraphs

Creators: Gonçalves, Daniel; Havet, Frédéric; Pinlou, Alexandre; Thomassé, Stéphan

Others:: Algorithmes, Graphes et Combinatoire (ALGCO) ; Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) ; Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS); Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA); Jaroslav Nešetřil and André Raspaud

Description

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.

Abstract

International audience

Spanning galaxies in digraphs

Description

Abstract

Additional details