On signed digraphs with all cycles negative

Abstract

It is known that signed graphs with all cycles negative are those in which each block is a negative cycle or a single line. We now study the more difficult problem for signed diagraphs. In particular we investigate the structure of those diagraphs whose arcs can be signed (positive or negative) so that every (directed) cycle is negative. Such diagraphs are important because they are associated with qualitatively nonsingular matrices. We identify certain families of such diagraphs and characterize those symmetric diagraphs which can be signed so that every cycle is negative.