Spectral radius and matchings in graphs
By Suil O. Linear Algebra and its Applications, 2021
125 citations recorded by the source corpus.
Abstract A perfect matching in a graph G is a set of disjoint edges covering all vertices of G. Let ρ ( G ) be the spectral radius of a graph G, and let θ ( n ) be the largest root of x 3 − ( n − 4 ) x 2 − ( n − 1 ) x + 2 ( n − 4 ) = 0 . In this paper, we prove that for a positive even integer n ≥ 8 or n = 4 , if G is an n-vertex graph with ρ ( G ) > θ ( n ) , then G has a perfect matching; for n = 6 , if ρ ( G ) > 1 + 33 2 , then G has a perfect matching. It is sharp for every positive even integer n ≥ 4 in the sense that there are graphs H with ρ ( H ) = θ ′ ( n ) and no perfect matching, where θ ′ ( n ) = θ ( n ) if n = 4 or n ≥ 8 and θ ′ ( 6 ) = 1 + 33 2 .
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/e9bc46fe7a4ec3c680d9545d3c6a3ad34de8c0bb
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- A survey on spectral conditions for some extremal graph problems (2021, background): “Moreover, Suil O [162] proved the following lower bound for spectral radius in an n-vertex graph to guarantee the existence of a perfect matching.”
- The spanning k-trees, perfect matchings and spectral radius of graphs (2021, background): “Very recently, O [17] provided a lower bound for the adjacency spectral radius which guarantees the existence of a perfect matching in a graph.”