Regular Factors of Regular Graphs from Eigenvalues

Source abstract

Let $r$ and $m$ be two integers such that $r\geq m$. Let $H$ be a graph with order $|H|$, size $e$ and maximum degree $r$ such that $2e\geq |H|r-m$. We find a best lower bound on spectral radius of graph $H$ in terms of $m$ and $r$. Let $G$ be a connected $r$-regular graph of order $|G|$ and $k < r$ be an integer. Using the previous results, we find some best upper bounds (in terms of $r$ and $k$) on the third largest eigenvalue that is sufficient to guarantee that $G$ has a $k$-factor when $k|G|$ is even. Moreover, we find a best bound on the second largest eigenvalue that is sufficient to guarantee that $G$ is $k$-critical when $k|G|$ is odd. Our results extend the work of Cioabă, Gregory and Haemers [J. Combin. Theory Ser. B, 1999] who obtained such results for 1-factors.