Antistrong digraphs

Abstract : An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alternate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices x, y in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. A digraph D is antistrong if it contains an antidirected (x, y)-trail starting and ending with a forward arc for every choice of x, y ∈ V (D) . We show that antistrong connectivity can be decided in linear time. We discuss relations between antistrong connectivity and other properties of a digraph and show that the arc-minimal antistrong spanning subgraphs of a digraph are the bases of a matroid on its arc-set. We show that one can determine in polynomial time the minimum number of new arcs whose addition to D makes the resulting digraph the arc-disjoint union of k antistrong digraphs. In particular, we determine the minimum number of new arcs which need to be added to a digraph to make it antistrong. We use results from matroid theory to characterize graphs which have an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. This immediately gives analogous results for graphs which have a connected bipartite 2-detachment. Finally, we study arc-decompositions of antistrong digraphs and pose several problems and conjectures.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2017, 122, pp.68-90. 〈10.1016/j.jctb.2016.05.004〉
Liste complète des métadonnées
Contributeur : Isabelle Gouat <>
Soumis le : mardi 26 juillet 2016 - 07:45:24
Dernière modification le : vendredi 16 novembre 2018 - 18:05:05
Document(s) archivé(s) le : jeudi 27 octobre 2016 - 10:40:10


Fichiers produits par l'(les) auteur(s)




Jørgen Bang-Jensen, Stéphane Bessy, Bill Jackson, Matthias Kriesell. Antistrong digraphs. Journal of Combinatorial Theory, Series B, Elsevier, 2017, 122, pp.68-90. 〈10.1016/j.jctb.2016.05.004〉. 〈lirmm-01348862〉



Consultations de la notice


Téléchargements de fichiers