Path coverings of graphs and height characteristics of matrices
type: Item
instance of: scholarly article
title: Path coverings of graphs and height characteristics of matrices
zbMATH Open document ID: 0794.05078
author: Daniel Hershkowitz
author: Hans Schneider
published in: Journal of Combinatorial Theory. Series B
publication date: 1994-08-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15A21
zbMATH DE Number: 562415
zbMATH Keywords: triangular graph
zbMATH Keywords: reduced graph
zbMATH Keywords: singular graph
zbMATH Keywords: singular length
zbMATH Keywords: generic matrix
zbMATH Keywords: height characteristic
zbMATH Keywords: triangular matrix
zbMATH Keywords: singular \(k\)-paths
zbMATH Keywords: dual sequence
zbMATH Keywords: sequence of differences
zbMATH Keywords: path coverings
zbMATH Keywords: acyclic graph
reviewed by: H. J. Schneider
MaRDI profile type: Publication
OpenAlex ID: W1988956154
DOI: 10.1006/JCTB.1993.1063
Recommended article: ON THE PATH MATRICES OF GRAPHS AND THEIR PROPERTIES
Recommended article: Dimension and height for posets with planar cover graphs
Recommended article: Nontrivial path covers of graphs: existence, minimization and maximization
Recommended article: Dimension and height for posets with planar cover graphs.
Recommended article: The covering number of the elements of a matroid and generalized matrix functions
Recommended article: Q3718758
Recommended article: Coverings of graphs and maps, orthogonality, and eigenvectors
Recommended article: Q4821188
Recommended article: Paths and cycles in matroid base graphs
Recommended article: Matchings, path covers and domination
description: scientific article; zbMATH DE number 562415