k-NIM trees: Characterization and Enumeration

MaRDI QIDQ6407534zbMATH OpenFDO

Authors C. Richard jun. Johnson, George Tsoukalas, Greyson C. Wesley, Zachary Zhao

Publication date 10 August 2022

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Hermitian, skew-Hermitian, and related matrices (15B57)

Abstract: 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 $kgeq1$, 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.

This page was built for publication: $k$-NIM trees: Characterization and Enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407534)