Antistrong digraphs

DOI10.1016/J.JCTB.2016.05.004MaRDI QIDQ345072zbMATHOpenAlexFDO

Authors Stéphane Bessy, Bill Jackson, Matthias Kriesell, Jørgen Bang-Jensen

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.07832

zbMATH Keywords

matroidanticonnected digraphantidirected pathbipartite representationdetachment

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of matroids and geometric lattices (05B35)

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,yinV(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.

Recommendations

• Anti-Eulerian digraphs
• scientific article; zbMATH DE number 1092941
• Antipodal graphs and digraphs
• The antistrong property for special digraph families
• Antimagic labeling of digraphs
• Ore conditions for antistrong digraphs
• Antimedian graphs
• On antimode graphs
• On antipodal graphs
• scientific article; zbMATH DE number 4145927

Cites work

• scientific article; zbMATH DE number 1092941 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A rooted-forest partition with uniform vertex demand
• Arc-disjoint spanning sub(di)graphs in digraphs
• Connected Detachments of Graphs and Generalized Euler Trails
• Connections in combinatorial optimization
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
• Digraphs
• Minimum partition of a matroid into independent subsets
• Signed graphs

Cited in

(9)

• Proper‐walk connection number of graphs
• Ore conditions for antistrong digraphs
• Reachability in choice networks
• Rainbow antistrong connection in tournaments
• Adamant digraphs
• Necessary and sufficient conditions for circulant digraphs to be antistrong, weakly-antistrong and anti-Eulerian
• The antistrong property for special digraph families
• scientific article; zbMATH DE number 5501202 (Why is no real title available?)
• Analyzing the reachability problem in choice networks

This page was built for publication: Antistrong digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345072)