A relation between multiplicity of nonzero eigenvalues and the matching number of graph

Abstract

Let $G$ be a graph with an adjacent matrix $A(G)$. The multiplicity of an arbitrary eigenvalue $\lambda$ of $A(G)$ is denoted by $m_{\lambda }(G)$. In \cite{Wong}, the author apply the Pater-Wiener Theorem to prove that if the diameter of $T$ at least $4$, then $m_{\lambda }(T)\le {\beta }^{\prime }(T)-1$ for any $\lambda \ne 0$. Moreover, they characterized all trees with $m_{\lambda }(T)={\beta }^{\prime }(T)-1$, where ${\beta }^{\prime }(G)$ is the induced matching number of $G$. In this paper, we intend to extend this result from trees to any connected graph. Contrary to the technique used in \cite{Wong}, we prove the following result mainly by employing algebraic methods: For any non-zero eigenvalue $\lambda$ of the connected graph $G$, $m_{\lambda }(G)\le {\beta }^{\prime }(G)+c(G)$, where $c(G)$ is the cyclomatic number of $G$, and the equality holds if and only if $G\cong C_3(a,a,a)$ or $G\cong C_5$, or a tree with the diameter is at most $3$. Furthermore, if ${\beta }^{\prime }(G)\ge 3$, we characterize all connected graphs with $m_{\lambda }(G)={\beta }^{\prime }(G)+c(G)-1$.