Enumeration of Minimum Path Covers of Trees

Abstract

In the study of possible multiplicity lists for eigenvalues of real symmetric matrices with a given tree T as graph, the value of maximum multiplicity, M(T), has been of great interest. M(T) turns out to be the same as P(T), the path cover number of T. This is the minimum number of induced paths of T that are vertex disjoint and cover all its vertices. For a given tree T , P(T) can be achieved in several ways. Here, we give a method to enumerate all possible minimum path covers for any given tree through a reductive procedure.