zbMATH — the first resource for mathematics

Spanning galaxies in digraphs. (English) Zbl 1273.05087
Nešetřil, Jaroslav (ed.) et al., Extended abstracts of the 5th European conference on combinatorics, graph theory and applications, EuroComb’09, Bordeaux, France, September 7–11, 2009. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 34, 139-143 (2009).
Summary: 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 $$\mathsf{dst}(D)$$, is the minimum number of galaxies needed to cover $$A(D)$$. In this paper, we show that $$\mathsf{dst}(D)\leq \Delta(D)+1$$ and that if $$D$$ is acyclic then $$\mathsf{dst}(D)\leq \Delta(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.
For the entire collection see [Zbl 1239.05008].
MSC:
 05C20 Directed graphs (digraphs), tournaments
Full Text:
References:
 [1] Algor, I.; Alon, N., The star arboricity of graphs, Discrete math., 75, 11-22, (1989) · Zbl 0684.05033 [2] O. Amini, F. Havet, F. Huc and S. Thomassé, WDM and directed star arboricity, to appear in Combinatorics, Probability and Computing · Zbl 1216.05044 [3] Guiduli, B., On incidence coloring and star arboricity of graphs, Discrete mathematics, 163, 275-278, (1997) · Zbl 0871.05022 [4] Kratochvíl, J., A special planar satisfiability problem and a consequence of its NP-completeness, Discrete applied mathematics, 52, 3, 233-252, (1994) · Zbl 0810.68083 [5] McCuaig, W., Pólya’s permanent problem, Electron. J. combin., 11, 1, (2004), Research Paper 79, 83 pp. (electronic) · Zbl 1062.05066 [6] Robertson, N.; Seymour, P.D.; Thomas, R., Permanents, Pfaffian orientations, and even directed circuits, Ann. of math. (2), 150, 3, 929-975, (1999) · Zbl 0947.05066 [7] Thomassen, C., Even cycles in directed graphs, European J. combin., 6, 1, 85-89, (1985) · Zbl 0606.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.