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

Abstract

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

CLC Number:

O157

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.

References

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]	TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths [J]. Operations Research Transactions, 2020, 24(1): 140-146.
[2]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.
[3]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[4]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[5]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[6]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[7]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[8]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[9]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[10]	YU Guidong, SUN Wei, LU Xingting. The least eignvalue of the graphs whose complements are connected and have pendant vertices [J]. Operations Research Transactions, 2019, 23(1): 90-96.
[11]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[12]	DING Chao, YU Guidong. Laplacian spectral characterizations of graphs with even cyclic [J]. Operations Research Transactions, 2018, 22(4): 135-140.
[13]	LV Xuezheng, WEI Erling, SONG Hongye. The basis number of join graphs [J]. Operations Research Transactions, 2018, 22(4): 148-152.
[14]	LI Li, SHAN Erfang. Graph games and edge density of graphs [J]. Operations Research Transactions, 2018, 22(4): 99-107.
[15]	QIN Qiannan, SHAO Yanling. Minimum general sum-connectivity index of tricyclic graphs [J]. Operations Research Transactions, 2018, 22(1): 142-150.

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

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments