Path coverings of graphs and height characteristics of matrices (Q1322029)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path coverings of graphs and height characteristics of matrices |
scientific article |
Statements
Path coverings of graphs and height characteristics of matrices (English)
0 references
28 August 1994
0 references
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.
0 references
triangular graph
0 references
reduced graph
0 references
singular graph
0 references
singular length
0 references
generic matrix
0 references
height characteristic
0 references
triangular matrix
0 references
singular \(k\)-paths
0 references
dual sequence
0 references
sequence of differences
0 references
path coverings
0 references
acyclic graph
0 references