Path coverings of graphs and height characteristics of matrices (Q1322029): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1988956154 / rank | |||
Normal rank |
Latest revision as of 23:57, 19 March 2024
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