Antistrong digraphs

DOI10.1016/J.JCTB.2016.05.004zbMATH Open1350.05048arXiv1605.07832OpenAlexW4212790289MaRDI QIDQ345072FDOQ345072

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)

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.

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

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 Keywords

matroidanticonnected digraphantidirected pathbipartite representationdetachment

Mathematics Subject Classification ID

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

Cites Work

• Signed graphs
• Connections in combinatorial optimization
• Title not available (Why is that?)
• Digraphs
• Minimum partition of a matroid into independent subsets
• Title not available (Why is that?)
• A rooted-forest partition with uniform vertex demand
• Arc-disjoint spanning sub(di)graphs in digraphs
• Connected Detachments of Graphs and Generalized Euler Trails
• Title not available (Why is that?)
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs

Cited In (9)

• The antistrong property for special digraph families
• Reachability in choice networks
• Adamant digraphs
• Rainbow antistrong connection in tournaments
• Analyzing the reachability problem in choice networks
• Title not available (Why is that?)
• Ore conditions for antistrong digraphs
• Proper‐walk connection number of graphs
• Necessary and sufficient conditions for circulant digraphs to be antistrong, weakly-antistrong and anti-Eulerian

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)