补图具有悬挂点且连通的图的最小特征值

doi:10.15960/j.cnki.issn.1007-6093.2019.01.010

Abstract

Abstract:

The least eigenvalue of the graph is defined as the smallest eigenvalue of 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 connected and have pendent vertices, and present the lower bound of the least eigenvalue of such classes of graphs.

Key words: graph, complement, adjacency matrix, the least eigenvalue

CLC Number:

O157

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.

References

[1] Bell F K, Cvetkovi? D, Rowlinson P, et al. Graph for which the least eigenvalues is minimal, I[J]. Linear Algebra and its Applications, 2008, 429:234-241.
[2] Bell F K, Cvetkovi? D, Rowlinson P, et al. Graph for which the least eigenvalues is minimal, Ⅱ[J]. Linear Algebra and its Applications, 2008, 429:2168-2176.
[3] Cardoso D M, Cvetkovi? D, Rowlinson P, et al. A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph[J]. Linear Algebra and its Applications, 2008, 429:2770-2780.
[4] Fan Y Z, Wang Y, Gao Y B. Minimizing the least eigenvalues of unicyclic graphs with application to spectral spread[J]. Linear Algebra and its Applications, 2008, 429:577-588.
[5] Liu R F, Zhai M X, Shu J L. The least eigenvalues of unicyclic graph with n vertices and k pendant vertices[J]. Linear Algebra and its Applications, 2009, 431:657-665.
[6] Petrovi? M, Borovi?anin B, Aleksi? T. Bicyclic graphs for which the least eigenvalue is minimum[J]. Linear Algebra and its Applications, 2009, 430:1328-1335.
[7] 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 and its Applications, 2010, 433:790-795.
[8] Wang Y, Fan Y Z. The least eigenvalue of a graph with cut vertices[J]. Linear Algebra and its Applications, 2010, 433:19-27.
[9] Ye M L, Fan Y Z, Liang D. The least eigenvalue of graphs with given connectivity[J]. Linear Algebra and its Applications, 2009, 430:1375-1379.
[10] Yu G D, Fan Y Z, Wang Yi. Quadratic forms on graphs with application to minimizing the least eigenvalue of signless Laplacian over bicyclic graphs[J]. Electronic Journal of Linear Algebra, 2014, 27:213-236.
[11] Fan Y Z, Zhang F F, Wang Y. The least eigenvalue of the complements of tree[J]. Linear Algebra and its Applications, 2011, 435:2150-2155.
[12] Wang Y, Fan Y Z, Li X X, et al. The least eigenvalue of graphs whose complements are unicyclic[J]. Discussiones Mathematicae Graph Theory, 2013, 35(2):1375-1379.
[13] Yu G D, Fan Y Z. The least eigenvalue of graphs[J]. 数学研究及应用, 2012, 32(6):659-665.
[14] Yu G D, Fan Y Z. The least eigenvalue of graphs whose complements are 2-vertex or 2-edge connected[J]. Operations Research Transactions, 2013, 17(2):81-88.
[15] Li S C, Wang S J. The least eigenvalue of the signless Laplacian of the complements of trees[J]. Linear Algebra and its Applications, 2012, 436:2398-2405.
[16] Yu G D, Fan Y Z, Ye M L. The least signless Laplacian eigenvalue of the complements of unicyclic graphs[J]. Applied Mathematics and Computation, 2017, 306:13-21.
[17] Haemers W. Interlacing eigenvalues and graphs[J]. Linear Algebra and its Applications, 1995, 227-228:593-616.

The least eignvalue of the graphs whose complements are connected and have pendant vertices

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	LIU Zhiping. Some advances in gene regulatory network inference [J]. Operations Research Transactions, 2021, 25(3): 173-182.
[2]	LAN Yongxin, SHI Yongtang, SONG Zixia. Planar Turán number and planar anti-Ramsey number of graphs [J]. Operations Research Transactions, 2021, 25(3): 200-216.
[3]	LIU Yao. On (1, 0)-relaxed strong edge-coloring of graphs [J]. Operations Research Transactions, 2021, 25(2): 115-126.
[4]	DONG Yanxia, XUE Tao, ZHANG Guang. k-tuple domination in generalized de Bruijn digraphs [J]. Operations Research Transactions, 2021, 25(2): 127-134.
[5]	BAO Xiaoguang, LU Chao, HUANG Dongmei, YU Wei. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[6]	ZHAO Jing, SHAN Erfang, ZHAO Jiagui. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131.
[7]	CHEN Min, YANG Jianmin, ZHANG Hao, WANG Yiting. Weakly entire coloring of outerplanar graphs [J]. Operations Research Transactions, 2021, 25(1): 132-136.
[8]	LIN Xiaoxia. A note on quasi k-connected graphs [J]. Operations Research Transactions, 2021, 25(1): 137-140.
[9]	YU Guidong, RUAN Zheng, SHU Axiu, YU Tao. The second maximum (Laplacian) separator of unicyclic graphs [J]. Operations Research Transactions, 2020, 24(4): 128-134.
[10]	TONG Linken, SHAN Erfang. The restricted edge-connectivity and λ'-optimality of hypergraphs [J]. Operations Research Transactions, 2020, 24(4): 145-152.
[11]	LIN Hao, LIN Lan. Optimality characterization of the minimum stretch spanning tree problem for interval graphs [J]. Operations Research Transactions, 2020, 24(4): 153-158.
[12]	CHEN Hongling, WANG Huijuan, SUN Fengyan, XUE Juan, GAO Hongwei. Linear arboricity of planar graphs with maximum degree at least seven [J]. Operations Research Transactions, 2020, 24(3): 154-160.
[13]	CHEN Tao. Upper bounds on minimum balanced bipartition of Hamilton plane graphs [J]. Operations Research Transactions, 2020, 24(3): 161-166.
[14]	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.
[15]	LI Tong, WANG Guanghui, ZHOU Wenling. A survey on rainbow matchings in graphs and hypergraphs [J]. Operations Research Transactions, 2019, 23(3): 77-90.