Spectral radius and matchings in graphs

被引:50
作者
Suil, O. [1 ]
机构
[1] State Univ New York, Dept Appl Math & Stat, Incheon 21985, South Korea
关键词
Spectral radius; Perfect matching;
D O I
10.1016/j.laa.2020.06.004
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A perfect matching in a graph G is a set of disjoint edges covering all vertices of G. Let rho(G) be the spectral radius of a graph G, and let theta(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 rho(G) > theta(n), then G has a perfect matching; for n = 6, if rho(G) > 1+root 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 rho(H) = theta'(n) and no perfect matching, where theta'(n) = theta(n) if n = 4 or n >= 8 and theta'(6) = 1+root 33/2. (C) 2020 Elsevier Inc. All rights reserved.
引用
收藏
页码:316 / 324
页数:9
相关论文
共 11 条