A matrix for counting paths in acyclic digraphs
type: Item
instance of: scholarly article
title: A matrix for counting paths in acyclic digraphs
zbMATH Open document ID: 0860.05054
author: Richard P. Stanley
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-07-09T00:00:00Z
review text: Let \(\Gamma\) be an acyclic digraph without multiple edges on the vertex set \(\{x_1,\dots,x_n\}\). Define the \(n\times n\)-matrix \(A=A_\Gamma\), putting \(A_{ij}=0\) if \((x_i,x_j)\) is an arc of \(\Gamma\) and \(A_{ij}=1\) otherwise. It is proved that the coefficient of \(z^k\) in the characteristic polynomial \(\text{det}(I+zA)\) is the number of \(j\)-vertex paths in \(\Gamma\).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 883810
zbMATH Keywords: matrix for counting paths
zbMATH Keywords: number paths
zbMATH Keywords: acyclic digraph
reviewed by: Regina Iosifovna Tyshkevich
MaRDI profile type: Publication
OpenAlex ID: W2125622766
DOI: 10.1006/JCTA.1996.0046
description: scientific article; zbMATH DE number 883810