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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01348862
Contributor : Isabelle Gouat <>
Submitted on : Tuesday, July 26, 2016 - 7:45:24 AM
Last modification on : Friday, November 16, 2018 - 6:05:05 PM
Long-term archiving on : Thursday, October 27, 2016 - 10:40:10 AM

File

antistrong.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

170

Files downloads

254