### Article Source

# Antistrong Digraphs

- Speaker: Jørgen Bang-Jensen
- Trimester Program: Combinatorial Optimization (10.09.2015)

## 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 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.