Trees with maximum nullity (Q1774973): Difference between revisions

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. Among all \(n\)-vertex trees, the star tree has greatest nullity (equal to \(n-2\)). In this paper it is shown that among all \(n\)-vertex trees whose vertex degrees do not exceed a fixed value \(D\), the greatest nullity is \(n- 2 \lceil (n-1)/D \rceil\). In addition, methods for constructing some such greatest nullity trees are presented, together with a conjectured description of these trees.