Characterizations of two classes of digraphs
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.
- A new characterization of proper interval graphs
- A structure theorem for the consecutive 1's property
- Betweenness, orders and interval graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Doubly Lexical Orderings of Matrices
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- Representation of a finite graph by a set of intervals on the real line
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Three Partition Refinement Algorithms
This page was built for publication: Characterizations of two classes of digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336693)
