Spectral radius and matchings in graphs

被引:61
作者
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 条
[1]   Eigenvalues and perfect matchings [J].
Brouwer, AE ;
Haemers, WH .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 395 :155-162
[2]  
Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6
[3]   Matchings in regular graphs from eigenvalues [J].
Cioaba, Sebastian M. ;
Gregory, David A. ;
Haemers, Willem H. .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (02) :287-297
[4]  
Godsil C., 2001, GRADUATE TEXTS MATH, V207
[5]   Tight lower bounds on the size of a maximum matching in a regular graph [J].
Henning, Michael A. ;
Yeo, Anders .
GRAPHS AND COMBINATORICS, 2007, 23 (06) :647-657
[6]   Matching and edge-connectivity in regular graphs [J].
O, Suil ;
West, Douglas B. .
EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (02) :324-329
[7]   Spectral radius and fractional matchings in graphs [J].
Suil, O. .
EUROPEAN JOURNAL OF COMBINATORICS, 2016, 55 :144-148
[8]   EDGE-CONNECTIVITY, EIGENVALUES, AND MATCHINGS IN REGULAR GRAPHS [J].
Suil, O. ;
Cioaba, Sebastian M. .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (04) :1470-1481
[9]   Balloons, Cut-Edges, Matchings, and Total Domination in Regular Graphs of Odd Degree [J].
Suil, O. ;
West, Douglas B. .
JOURNAL OF GRAPH THEORY, 2010, 64 (02) :116-131
[10]  
Tutte W.T, 1947, J. Lond. Math. Soc., V22, P107, DOI DOI 10.1112/JLMS/S1-22.2.107