A characterization of graphs $G$ with nullity $n(G)-d(G)-1$

Abstract

For a connected graph $G$ with order $n$, let $e(G)$ represent the number of its distinct eigenvalues, and let $d$ denote its diameter. We denote the eigenvalue multiplicity of $\mu$ in $G$ by $m_G(\mu )$. It is well established that the inequality $e(G)\ge d+1$ implies that when $\mu$ is an eigenvalue of $P_{d+1}$, it follows that $m_G(\mu )\le n-d$; otherwise, for any real number $\mu$, we have $m_G(\mu )\le n-d-1$. A graph is termed minimal if $e(G)=d+1$. In 2013, Wong et al. characterized all minimal graphs for which $m_G(0)=n-d$. In this article, we provide a complete characterization of the graphs $G$ such that $m_G(0)=n-d-1$.

arXiv commentarXiv admin note: text overlap with arXiv:2410.15000