Hershkowitz, Daniel; Schneider, Hans Path coverings of graphs and height characteristics of matrices. (English) Zbl 0794.05078 J. Comb. Theory, Ser. B 59, No. 2, 172-187 (1993). Using graph theoretic techniques, it is shown that the height characteristic of a triangular matrix \(A\) majorizes the dual sequence of the sequence of differences of maximal cardinalities of singular \(k\)- paths in the graph \(G(A)\) of \(A\), and that in the generic case the height characteristic is equal to that dual sequence. The results on matrices are also used to prove a graph theoretic result on the duality of the sequence of differences of minimal \(k\)th norms of path coverings for a (0-1)-weighted acyclic graph \(G\) and the sequence of differences of maximal cardinalities of \(k\)-paths in \(G\). This results generalizes known results on unweighted graphs. Reviewer: H.Schneider (Madison) Cited in 7 Documents MSC: 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 15A15 Determinants, permanents, traces, other special matrix functions 15A21 Canonical forms, reductions, classification Keywords:triangular graph; reduced graph; singular graph; singular length; generic matrix; height characteristic; triangular matrix; singular \(k\)-paths; dual sequence; sequence of differences; path coverings; acyclic graph PDFBibTeX XMLCite \textit{D. Hershkowitz} and \textit{H. Schneider}, J. Comb. Theory, Ser. B 59, No. 2, 172--187 (1993; Zbl 0794.05078) Full Text: DOI Link