Binding Number, $k$-Factor and Spectral Radius of Graphs

Source abstract

The binding number $b(G)$ of a graph $G$ is the minimum value of $|N_{G}(X)|/|X|$ taken over all non-empty subsets $X$ of $V(G)$ such that $N_{G}(X)\neq V(G)$. The association between the binding number and toughness is intricately interconnected, as both metrics function as pivotal indicators for quantifying the vulnerability of a graph. The Brouwer-Gu Theorem asserts that for any $d$-regular connected graph $G$, the toughness $t(G)$ always at least $\frac{d}{\lambda}-1$, where $\lambda$ denotes the second largest absolute eigenvalue of the adjacency matrix. Inspired by the work of Brouwer and Gu, in this paper, we investigate $b(G)$ from spectral perspectives, and provide tight sufficient conditions in terms of the spectral radius of a graph $G$ to guarantee $b(G)\geq r$. The study of the existence of $k$-factors in graphs is a classic problem in graph theory. Katerinis and Woodall state that every graph with order $n\geq 4k-6$ satisfying $b(G)\geq 2$ contains a $k$-factor where $k\geq 2$. This leaves the following question: which $1$-binding graphs have a $k$-factor? In this paper, we also provide the spectral radius conditions of $1$-binding graphs to contain a perfect matching and a $2$-factor, respectively.