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

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

运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 90-96.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.010

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

余桂东^1,2,*, 孙威¹, 芦兴庭¹

1. 安庆师范大学数学与计算科学学院, 安徽安庆 246133;
2. 合肥幼儿师范高等专科学校基础部, 合肥 230013

收稿日期:2017-03-09 出版日期:2019-03-15 发布日期:2019-03-15
通讯作者: 余桂东 E-mail:guidongy@163.com
基金资助:
国家自然科学基金（No.11671164），安徽省自然科学基金（No.1808085MA04），安徽省高校自然科学基金（No.KJ2017A362）

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

YU Guidong^1,2,*, SUN Wei¹, LU Xingting¹

1. School of Mathematics and Computation Sciences, Anqing Normal University, Anqing 246133, Anhui, China;
2. Basic Department, Hefei Preschool Education College, Hefei 230013, China

Received:2017-03-09 Online:2019-03-15 Published:2019-03-15

摘要/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

中图分类号:

O157

余桂东, 孙威, 芦兴庭. 补图具有悬挂点且连通的图的最小特征值[J]. 运筹学学报, 2019, 23(1): 90-96.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘治平. 基因调控网络推断研究进展[J]. 运筹学学报, 2021, 25(3): 173-182.
[2]	兰永新, 史永堂, 宋梓霞. 图的平面Turán数和平面anti-Ramsey数[J]. 运筹学学报, 2021, 25(3): 200-216.
[3]	刘瑶. 带松弛条件的图的强边着色[J]. 运筹学学报, 2021, 25(2): 115-126.
[4]	董艳侠, 薛涛, 张广. 广义de Bruijn有向图的k-元控制集[J]. 运筹学学报, 2021, 25(2): 127-134.
[5]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[6]	赵静, 单而芳, 赵加贵. 最大边连通和super-边连通超图的充分条件[J]. 运筹学学报, 2021, 25(1): 123-131.
[7]	陈敏, 杨建民, 张豪, 王依婷. 外平面图的弱完备染色[J]. 运筹学学报, 2021, 25(1): 132-136.
[8]	林晓霞. 关于拟$k$-连通图的一个注释[J]. 运筹学学报, 2021, 25(1): 137-140.
[9]	余桂东, 阮征, 舒阿秀, 于涛. 单圈图的次大(拉普拉斯)分离度[J]. 运筹学学报, 2020, 24(4): 128-134.
[10]	王娅静, 高玉斌. 具有较大Randić指数的仙人掌图[J]. 运筹学学报, 2020, 24(4): 135-144.
[11]	童林肯, 单而芳. 超图的限制边连通度与最优限制边连通[J]. 运筹学学报, 2020, 24(4): 145-152.
[12]	林浩, 林澜. 区间图最小伸展支撑树问题的最优性刻画[J]. 运筹学学报, 2020, 24(4): 153-158.
[13]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[14]	陈涛. 哈密尔顿平面图最小平衡二部划分的上界[J]. 运筹学学报, 2020, 24(3): 161-166.
[15]	李瞳, 王光辉, 周文玲. 图与超图中的彩色匹配综述[J]. 运筹学学报, 2019, 23(3): 77-90.