Communications of the
Korean Mathematical Society CKMS

For a given graph $G$ we consider a set $S(G)$ of all symmetric matrices $A=[a_{ij}]$ whose nonzero entries are placed according to the location of the edges of the graph, i.e., for $i \ne j$, $a_{ij} \ne 0$ if and only if vertex $i$ is adjacent to vertex $j$. The minimum rank ${\rm mr}(G)$ of the graph $G$ is defined to be the smallest rank of a matrix in $S(G)$. In general the computation of ${\rm mr}(G)$ is complicated, and so is that of the maximum multiplicity ${\rm MaxMult}(G)$ of an eigenvalue of a matrix in $S(G)$ which is equal to $n -{\rm mr}(G)$ where $n$ is the number of vertices in $G$. However, for trees $T$, there is a recursive formula to compute ${\rm MaxMult}(T)$. In this note we show that this recursive formula for ${\rm MaxMult}(T)$ also computes the path cover number $p(T)$ of the tree $T$. This gives an alternative proof of the interesting result, ${\rm MaxMult}(T)=p(T)$.

Keywords: maximum corank, maximum multiplicity, minimum rank, path cover number, tree

MSC numbers: Primary 05C50, 15A18