Characterizations of two classes of digraphs (Q1336693)

If the rows of a binary matrix can be permuted so that the ones in each column appear consecutively the matrix is said to have the consecutive ones property for columns. Three vertices \(x\), \(y\), \(z\) in a digraph form an astral triple if between any two of them there exists a chain \(P\) such that the third vertex of the triple does not belong to \(P\) and if the output degree of some vertex of \(P\) is nonzero there is no arc from this vertex to the third vertex of the triple. The author proves: The augmented adjacency matrix of a digraph \(G\) has the consecutive ones property for columns if and only if \(G\) does not contain an astral triple. A second characterization of a class of digraphs based on forbidden circuits is also established.