Antistrong digraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Combinatorial Theory, Series B Year : 2017

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.
Fichier principal
Vignette du fichier
antistrong.pdf (412.05 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01348862 , version 1 (26-07-2016)

Identifiers

Cite

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

Altmetric

Share

More