Binding number, k-factor and spectral radius of graphs
Summary: 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 \textit{A. E. Brouwer} [Linear Algebra Appl. 226--228, 267--271 (1995; Zbl 0833.05048)] and \textit{X. Gu} [SIAM J. Discrete Math. 35, No. 2, 948--952 (2021; Zbl 1465.05102), 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)\geqslant r\). The study of the existence of \(k\)-factors in graphs is a classic problem in graph theory. \textit{P. Katerinis} and \textit{D. R. Woodall} [Q. J. Math., Oxf. II. Ser. 38, 221--228 (1987; Zbl 0639.05050)] state that every graph with order \(n\geqslant 4k-6\) satisfying \(b(G)\geqslant 2\) contains a \(k\)-factor where \(k\geqslant 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.
- A bound on the spectral radius of graphs
- A proof of Brouwer's toughness conjecture
- A sharp upper bound of the spectral radius of graphs
- Best monotone degree conditions for binding number
- Binding number, minimum degree, and cycle structure in graphs
- Binding numbers and f-factors of graphs
- BINDING NUMBERS OF GRAPHS AND THE EXISTENCE OF k-FACTORS
- Eigenvalues and perfect matchings
- Graph toughness from Laplacian eigenvalues
- scientific article; zbMATH DE number 997668 (Why is no real title available?)
- Large matchings from eigenvalues
- Matchings in regular graphs from eigenvalues
- On the spectral radius of graphs with cut edges
- On the Toughness of a Graph
- Perfect matchings of a graph
- Perfect matchings, eigenvalues and expansion
- Proof of a conjecture on the spectral radius condition for \([a,b]\)-factors
- Sharp conditions for the existence of an even \([a,b]\)-factor in a graph
- Some Inequalities for the Largest Eigenvalue of a Graph
- Spectral radius and \([a,b]\)-factors in graphs
- Spectral radius and matchings in graphs
- The binding number of a graph and its Anderson number
- The Factorization of Linear Graphs
- The Factors of Graphs
- Tough Ramsey graphs without short cycles
- Toughness and binding number
- Toughness and spectrum of a graph
- Toughness in pseudo-random graphs
- Toughness, Hamiltonicity and spectral radius in graphs
- Binding number, odd \([1, b]\)-factors and the distance spectral radius
- Spectral radius, odd \([1, b]\)-factor and spanning \(k\)-tree of 1-binding graphs
- Spectral conditions for path-factors in isolated tough graphs
- Spectral radius, the matching number and fractional criticality of graphs
- A spectral condition for Hamilton cycles in tough bipartite graphs
- Spectral extremal problems on factors in tough graphs, and beyond
- Bipartite binding number, k-factor and spectral radius of bipartite graphs
- Sufficient conditions on the existence of factors in graphs involving minimum degree.
- Spectral radius and perfect matching in graphs with given fractional property
- Sufficient conditions for even factors in graphs
- A note on the spectral radius and \([a,b]\)-factor of graphs
- Spectral conditions for graphs to contain k-factors
- Eigenvalues and factors: a survey
- Spectral radius and critical covered graphs
- Tight spectral and size conditions for (fractional) (a, b; k)-critical graphs
- The existence of even factors based on the A_-spectral radius of graphs
- Extremal results for graphs with binding number strictly less than 1/r
This page was built for publication: Binding number, \(k\)-factor and spectral radius of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6197802)
