Regular factors of regular graphs from eigenvalues

Hongliang Lu

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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.

Détail

DOI : 10.37236/431

Classification : 05C50, 05C70
Mots-clés : lower bound, best upper bound, third largest eigenvalue, second largest eigenvalue