Trees with maximum nullity Original Research Article

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. Among n-vertex trees, the star has greatest nullity (equal to n − 2). We generalize this by showing that among n-vertex trees whose vertex degrees do not exceed a certain value D, the greatest nullity is n − 2left ceiling(n − 1)/Dright ceiling. Methods for constructing such maximum-nullity trees are described.