- ALGORITHMIC PROOF OF MaxMult(T) = p(T)
- ㆍ 저자명
- Kim. In-Jae
- ㆍ 간행물명
- Communications of the Korean Mathematical Society
- ㆍ 권/호정보
- 2012년|27권 4호|pp.665-668 (4 pages)
- ㆍ 발행정보
- 대한수학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
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{ eq}j$, $a_{ij}{ eq}0$ if and only if vertex $i$ is adjacent to vertex $j$. The minimum rank mr(G) of the graph G is defined to be the smallest rank of a matrix in S(G). In general the computation of mr(G) is complicated, and so is that of the maximum multiplicity MaxMult(G) of an eigenvalue of a matrix in S(G) which is equal to $n$ - mr(G) where n is the number of vertices in G. However, for trees T, there is a recursive formula to compute MaxMult(T). In this note we show that this recursive formula for MaxMult(T) also computes the path cover number $p$(T) of the tree T. This gives an alternative proof of the interesting result, MaxMult(T) = $p$(T).