Spectral radius of graphs with given matching number

被引：66
作者：
Feng, Lihua
Yu, Guihai
Zhang, Xiao-Dong
机构：
[1] Shandong Inst Business & Technol, Sch Math, Shandong 264005, Peoples R China
[2] Shanghai Jiao Tong Univ, Dept Math, Shanghai 200240, Peoples R China
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2007年 / 422卷 / 01期
基金：
上海市自然科学基金; 中国国家自然科学基金;
关键词：
graph; matching number; spectral radius;
D O I：
10.1016/j.laa.2006.09.014
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we show that of all graphs of order n with matching number, the graphs with maximal spectral radius are K-n if n = 2 beta or 2 beta + 1; K2 beta+1 boolean OR (Kn-2 beta-1) over bar if 2 beta + 2 <= n < 3 beta + 2; K-beta V K ((n-beta)) over bar or K2 beta+1 boolean OR (Kn-2 beta-1) over bar if n = 3 beta + 2; K-beta V Kn-beta if n > 3 beta + 2, where K-t is the empty graph on t vertices. (c) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码：133 / 138
页数：6
相关论文
共 12 条
[1]  
BERGE C, 1958, CR HEBD ACAD SCI, V247, P258
[2]   On the spectral radius of graphs with cut vertices [J].
Berman, A ;
Zhang, XD .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 83 (02) :233-240
[3]  
Bondy J. A., 1976, Graph theory with applications
[4]   ON THE SPECTRAL-RADIUS OF COMPLEMENTARY ACYCLIC MATRICES OF ZEROS AND ONES [J].
BRUALDI, RA ;
SOLHEID, ES .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :265-272
[5]  
Cvetkovic D. M., 1980, Spectra of Graphs-Theory and Application
[6]   INVERSES OF TREES [J].
GODSIL, CD .
COMBINATORICA, 1985, 5 (01) :33-39
[7]   On the Laplacian spectral radius of a tree [J].
Guo, JM .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 368 :379-385
[8]   Bounds on the largest eigenvalues of trees with a given size of matching [J].
Hou, YP ;
Li, JS .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2002, 342 (1-3) :203-217
[9]   On the spectral radius of graphs with cut edges [J].
Liu, HQ ;
Lu, M ;
Tian, F .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2004, 389 :139-145
[10]  
Lovasz L., 1986, Matching Theory (Annals of Discrete Mathematics)
12