×

Path coverings of graphs and height characteristics of matrices. (English) Zbl 0794.05078

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.

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
PDFBibTeX XMLCite
Full Text: DOI Link