Nonsingular acyclic matrices with an extremal number of P-vertices

It is known that for any nonsingular acyclic matrix of order n, the maximum number of P-vertices is n if n is even, and n-1 if n is odd. In this paper, we thoroughly characterize the trees where those bounds are achieved. In addition, for those trees and for any nonnegative integer k less than or equal to the extremal number of P-vertices, we provide an algorithm to construct a nonsingular matrix whose graph is the given tree and the number of P-vertices is k. Illustrative examples are given. (C) 2013 Elsevier Inc. All rights reserved.