\(k\)-NIM Trees: A Characterization and Enumeration
arXiv preprint, 2022
Among those real symmetric matrices whose graph is a given tree \(T\), the maximum multiplicity \(M(T)\) that can be attained by an eigenvalue is known to be the path cover number of \(T\). We say that a tree is \(k\)-NIM if, whenever an eigenvalue attains a multiplicity of \(k-1\) less than the maximum multiplicity, all other multiplicities are 1. 1-NIM trees are known as NIM trees, and a characterization for NIM trees is already known. Here we provide a graph-theoretic characterization for \(k\)-NIM trees for each \(k \geq 1\), as well as count them. It follows from the characterization that \(k\)-NIM trees exist on \(n\) vertices only when \(k=1,2,3\). In case \(k=3\), the only 3 -NIM trees are simple stars.
Recommended citation: C. R. Johnson, G. Tsoukalas, G. Wesley, and Z. Zhao. "\(k\)-NIM Trees: A Characterization and Enumeration" 2022. Preprint.
Download Paper