补图为2-点或2-边连通的图的最小特征值

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 81-88.

补图为2-点或2-边连通的图的最小特征值

余桂东^1,2，范益政^1,*

1. 安徽大学数学科学学院, 合肥 230601 2. 安庆师范学院数字与计算机科学学院, 安徽安庆 246011

收稿日期:2012-05-03 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 范益政 E-mail:fanyz@ahu.edu.cn

The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected

YU Guidong^1,2,FAN Yizheng^1,*

1. School of Mathematical Sciences, Anhui University, Hefei 230601, China 2. School of Mathematics and Computation Sciences, Anqing Normal College, Anqing 246011, Anhui, China

Received:2012-05-03 Online:2013-06-15 Published:2013-06-15

摘要/Abstract

摘要： 图的最小特征值定义为图的邻接矩阵的最小特征值，是刻画图结构性质的一个重要代数参数. 在所有给定阶数的补图为2-点或2-边连通的图中, 刻画了最小特征值达到极小的唯一图, 并给出了这类图最小特征值的下界.

关键词: 图, 2-点连通, 2-边连通, 邻接矩阵, 最小特征值

Abstract: The least eigenvalue of a graph is defined as the least eigenvalue of the adjacency matrix of the graph, which is an important algebraic parameter on characterizing structural property of graphs. In this paper we characterize the unique graph with the minimum least eigenvalue among all graphs of fixed order whose complements are 2-vertex connected or 2-edge connected, and present a lower bound for the least eigenvalue of such graphs.

Key words: graph, 2-vertex connected, 2-edge connected, adjacency matrix, least eigenvalue

中图分类号:

O157

余桂东，范益政. 补图为2-点或2-边连通的图的最小特征值[J]. 运筹学学报, 2013, 17(2): 81-88.

YU Guidong,FAN Yizheng. The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected[J]. Operations Research Transactions, 2013, 17(2): 81-88.

参考文献

Brualdi R A, Hoffman A J. On the Spectral radius (0,1)-matrix [J]. Linear Algebra Appl, 1985, 65: 133-146.
Cvetkovic D, Rowlinson P. The largest eigenvalues of a graph: a survey [J]. Linear Multilinear Algebra, 1990, 28: 3-33.
Cvetkovic D, Doob M, Sachs H. Spectra of Graphs [M]. 3rd Ed. Heidelberg: Johann Ambrosius Barth, 1995.
Cvetkovic D, Rowlinson P, Simic S. Spectral Generalizations of Line graphs: On graph with least eigenvalue-2 [M]. Cambridge: Cambridge University Press, 2004.
Hong Y, Shu J. Sharp lower bounds of the least eigenvalue of planar graphs [J]. Linear Algebra Appl, 1999, 296: 227-232.
Bell F K, Cvetkovic D, Rowlinson P, et al. Graph for which the least eigenvalues is minimal, I [J]. Linear Algebra Appl, 2008, 429: 234-241.
Bell F K, Cvetkovic D, Rowlinson P, et al. Graph for which the least eigenvalues is minimal, II [J]. Linear Algebra Appl, 2008, 429: 2168-2176.
Fan Y Z, Wang Y, Gao Y B. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread [J]. Linear Algebra Appl, 2008, 429: 577-588.
Ye M L, Fan Y Z, Liang D. The least eigenvalue of graphs with given connectivity [J]. Linear Algebra Appl, 2009, 430: 1375-1379.
Liu R, Zhai M, Shu J. The least eigenvalues of unicyclic graph with n vertices and k pendant vertices [J]. Linear Algebra Appl, 2009, 431: 657-665.
Petrovic M, Borovicanin B, Aleksic T. Bicyclic graphs for which the least eigenvalue is minimum [J]. Linear Algebra Appl, 2009, 430: 1328-1335.
Wang Y, Fan Y Z. The least eigenvalue of a graph with cut vertices [J]. Linear Algebra Appl, 2010, 433: 19-27.
Wang Y, Qiao Y, Fan Y Z. On the least eigenvalue of graphs with cut vertices [J]. J Math Res Expo, 2010, 30: 951-956.
Tan Y Y, Fan Y Z. The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph [J]. Linear Algebra Appl, 2010, 433: 790-795.
Constantine G. Lower bounds on the spectra of symmetric matrices with nonnegative entries [J]. Linear Algebra Appl, 1985, 65: 171-178.
Yu G D, Fan Y Z. The least eigenvalue of graphs [J]. J Math Res Expo, 2012, 32: 659-665.
Fan Y Z, Zhang F F, Wang Y. The least eigenvalue of the complements of tree [J]. Linear Algebra Appl,2011, 435: 2150-2155.
Li S, Wang S. The least eigenvalue of the signless Laplacian of the complements of trees [J]. Linear Algebra Appl, doi:10.1016/j.laa.2011.09.032.
Haemers W. Interlacing eigenvalues and graphs [J]. Linear Algebra Appl, 1995, 227-228, 593-616.

[1]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.
[2]	马丽涛, 边伟. 最优传输理论在图像处理中的应用[J]. 运筹学学报, 2019, 23(3): 109-125.
[3]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[4]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[5]	罗朝阳, 孙林. 6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报, 2019, 23(2): 113-119.
[6]	裴建峰, 林上为. 极大限制边连通超图的两个充分条件[J]. 运筹学学报, 2019, 23(2): 120-126.
[7]	孙秋实, 杨筱韵, 王力工, 李希赫, 王朋超. 新单圈图H(p,tK_1,m)的拉普拉斯谱刻画[J]. 运筹学学报, 2019, 23(1): 72-80.
[8]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[9]	陈宏宇, 谭香. 不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界[J]. 运筹学学报, 2019, 23(1): 104-110.
[10]	余桂东, 孙威, 芦兴庭. 补图具有悬挂点且连通的图的最小特征值[J]. 运筹学学报, 2019, 23(1): 90-96.
[11]	任佳敏, 冯伟, 赵凌琪, 王世英, 吉日木图. 单圈图生成的凯莱图UG_n在PMC模型和MM^*模型下的1好邻诊断度[J]. 运筹学学报, 2019, 23(1): 97-103.
[12]	丁超, 余桂东. 含偶圈图的Laplacian 谱刻画[J]. 运筹学学报, 2018, 22(4): 135-140.
[13]	吕雪征, 魏二玲, 宋宏业. 联图的圈基[J]. 运筹学学报, 2018, 22(4): 148-152.
[14]	李理, 单而芳. 图上合作博弈和图的边密度[J]. 运筹学学报, 2018, 22(4): 99-107.
[15]	王硕, 朱志斌, 张本鑫. 最小化三个凸函数之和的一个简单原始-对偶算法[J]. 运筹学学报, 2018, 22(2): 127-138.