链图的距离特征值

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

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (1): 112-120.doi: 10.15960/j.cnki.issn.1007-6093.2024.01.009

链图的距离特征值

吕雪征¹, 马梦郁¹^,*()

1. 中国人民大学数学学院, 北京 100872

收稿日期:2020-12-25 出版日期:2024-03-15 发布日期:2024-03-15
通讯作者: 马梦郁 E-mail:senorita@ruc.edu.cn
基金资助:
国家自然科学基金(11971479)

The distance spectra of chain graphs

Xuezheng LYU¹, Mengyu MA¹^,*()

1. School of Mathematics, Renmin University of China, Beijing 100872, China

Received:2020-12-25 Online:2024-03-15 Published:2024-03-15
Contact: Mengyu MA E-mail:senorita@ruc.edu.cn

摘要/Abstract

摘要：

如果一个图G不包含2K₂, C₃及C₅作为导出子图, 称其为链图。在所有点数和边数给定的连通二部图中, 链图具有最大的谱半径, 这使得链图在图谱理论中占有一席之地。本文研究了连通链图距离特征值的分布情况。对于点数为n的连通链图G=G(t₁, …, t_h; s₁, …, s_h), 我们证明了-2是G的重数为n-2h的距离特征值, 且G有h-1个距离特征值小于-2和h+1个距离特征值大于-2。

关键词: 链图, 距离特征值, 合理划分

Abstract:

A graph is called a chain graph if it does not contain induced $2K_2$, $C_3$ or $C_5$. In spectral graph theory, chain graphs feature as graphs whose largest eigenvalue within the connected bipartite graphs of fixed order and size is maximal. In this paper, we consider the distance eigenvalues of a connected chain graph $G$. We present that $-2$ is an eigenvalue of $G=G(t_1,\cdots,t_h; s_1,\cdots,s_h)$, with multiplicity $n-2h$. And further more, there are exactly $h-1$ eigenvalues less than -2 and exactly $h+1$ eigenvalues greater than -2.

Key words: chain graphs, distance spectrum, equitable partition

中图分类号:

O221.2

吕雪征, 马梦郁. 链图的距离特征值[J]. 运筹学学报（中英文）, 2024, 28(1): 112-120.

Xuezheng LYU, Mengyu MA. The distance spectra of chain graphs[J]. Operations Research Transactions, 2024, 28(1): 112-120.

图/表 2

1	Aouchiche M , Hansen P . Distance spectra of graphs: A survey[J]. Linear Algebra and Its Applications, 2014, 458, 301- 384. doi: 10.1016/j.laa.2014.06.010
2	Aouchiche M , Hansen P . Distance spectra of graphs: A survey[J]. Linear Algebra and Its Applications, 2014, 458, 301- 386. doi: 10.1016/j.laa.2014.06.010
3	Lin H , Shu J , Xue J , et al. A survey on distance spectra of graphs[J]. Advances in Mathematics, 2021, 50, 29- 76.
4	Andelić M , Andrade E , Cardoso D M , et al. Some new considerations about double nested graphs[J]. Linear Algebra and Its Applications, 2015, 483, 323- 341. doi: 10.1016/j.laa.2015.06.010
5	Bell F K , Cvetkovic , Rowlinson P , et al. Graphs for which the least eigenvalue is minimal[J]. Linear Algebra and Its Applications, 2008, 429, 2168- 2179. doi: 10.1016/j.laa.2008.06.018
6	Staniczenko P , Kopp J , Allesina S . The ghost of nestedness in ecological networks[J]. Nature Communications, 2013, 4, 1391. doi: 10.1038/ncomms2422
7	Alazemi A , Andelic M , Simic S K . Eigenvalue location for chain graphs[J]. Linear Algebra and Its Applications, 2016, 505, 194- 210. doi: 10.1016/j.laa.2016.04.030
8	Das K C , Alazemi A , Andelic M . On energy and Laplacian energy of chain graphs[J]. Discrete Applied Mathematics, 2020, 284, 391- 400. doi: 10.1016/j.dam.2020.03.057
9	Lu L , Huang Q X , Lou Z Z . On the distance spectra of threshold graphs[J]. Linear Algebra and Its Applications, 2018, 553, 223- 237. doi: 10.1016/j.laa.2018.05.014
10	Lou Z , Lin H . Distance eigenvalues of a cograph and their multiplicities[J]. Linear Algebra and Its Applications, 2021, 608, 1- 12. doi: 10.1016/j.laa.2020.08.016
11	Brouwer A E , Haemers W H . Spectra of Graphs[M]. Heidelberg: Spinger, 2012.
12	Godsil C D , Royel G . Algebraic Graph Theory[M]. Berlin: Springer-Verlag, 2001.
13	Lu L , Huang Q X , Huang X Y . The graphs with exactly two distance eigenvalues different from -1 and -3[J]. Journal of Algebraic Combinatorics, 2017, 45, 629- 647. doi: 10.1007/s10801-016-0718-2
14	Bondy J A , Murty U S R . Graph Theory[M]. New York: Springer, 2008.
15	König M D , Tessone C J , Zenou Y . Nestedness in networks: A theoretical model and some applications[J]. Theoretical Economics, 2014, 9, 695- 752. doi: 10.3982/TE1348
16	Lou Z Z , Wang J F , Huang Q X . On the eigenvalues distribution in threshold graphs[J]. Graphs and Combinatorics, 2019, 35, 867- 880. doi: 10.1007/s00373-019-02042-1

阶数	$ \left(t_1, \cdots, t_h; s_1, \cdots, s_h\right) $	距离谱
5	$ \left(1;4\right) $	{6.61, $ - $0.61, $ (-2)^3 $}
5	$ \left(1, 2;1, 1\right) $	{7.46, $ - $0.51, $ - $1.08, $ - $2, $ - $3.86}
5	$ \left(2, 1;1, 1\right) $	{6.54, 0, $ - $1.05, $ - $2, $ - $3.48}
6	$ \left(1, 1, 1;1, 1, 1\right) $	{9.26, 0, $ - $1, $ - $1.09, $ - $3.17, $ - $4}
6	$ \left(2, 1;1, 2\right) $	{8.57, 0.36, $ - $1, $ (-2)^2 $, $ - $3.93}
6	$ \left(2, 2;1, 1\right) $	{8.90, 0, $ - $0.9, $ (-2)^2 $, $ - $4}
6	$ \left(3;3\right) $	{7, 1, $ (-2)^4 $}
7	$ \left(1, 1, 1;1, 1, 2\right) $	{11.77, 0, $ - $0.85, $ - $1.07, $ - $2, $ - $3.26, $ - $4.59}
7	$ \left(2, 1, 1;1, 1, 1\right) $	{10.53, 0.58, $ - $0.77, $ - $1.03, $ - $2, $ - $3.19, $ - $4.12}
7	$ \left(2, 2;1, 2\right) $	{11.19, 0.36, $ - $0.85, $ (-2)^3 $, $ - $4.69}
7	$ \left(4;3\right) $	{8.61, 1.39, $ (-2)^5 $}
8	$ \left(4;4\right) $	{10, 2, $ (-2)^6 $}
8	$ \left(2, 2;2, 2\right) $	{12.32, 0.83, $ - $0.32, $ (-2)^4 $, $ - $4.83}

[1]	王祥丰, 曾尚志, 张进, 周金川. 面向非凸非光滑最优化问题的临近类方法寻找“钝化”局部最优解[J]. 运筹学学报（中英文）, 2026, 30(2): 1-23.
[2]	门彦超, 郦旭东. OWL1范数约束回归模型的快速算法[J]. 运筹学学报（中英文）, 2026, 30(2): 24-44.
[3]	曾静, 向耀, 张文燕. 交通均衡问题的适定性[J]. 运筹学学报（中英文）, 2026, 30(2): 58-68.
[4]	王峰, 杭波, 黄金洲, 徐德刚, 张泽宇, 刘佳谋. 一种基于动态情境感知的旅游路径规划方法[J]. 运筹学学报（中英文）, 2026, 30(2): 69-78.
[5]	吴晓宇, 邵虎, 刘鹏杰, 周金诚. 两个充分下降的RMIL型共轭梯度法及图像去噪应用[J]. 运筹学学报（中英文）, 2026, 30(2): 79-92.
[6]	崔恒鑫, 姜帆. 求解单调变分不等式的非精确邻近点算法与投影算法[J]. 运筹学学报（中英文）, 2026, 30(2): 194-208.
[7]	张雪峰, 彭潇, 陈良育, 杨争峰, 曾振柄. 面向混合整数线性规划问题的智能分支定界算法综述[J]. 运筹学学报（中英文）, 2026, 30(2): 237-270.
[8]	魏佳祯, 边伟. 共识优化算法的研究进展综述[J]. 运筹学学报（中英文）, 2026, 30(1): 1-23.
[9]	周允旭, 姚凡军, 高红伟. 区块链赋能数字化转型: 供应链协同运营策略研究[J]. 运筹学学报（中英文）, 2026, 30(1): 61-74.
[10]	赵弘欣, 孔令臣. 分散化投资组合的优化模型和方法研究[J]. 运筹学学报（中英文）, 2026, 30(1): 75-92.
[11]	孙珂, 王金亭, 王钟彬. 基于“排队等待区域娱乐”的经济效益分析[J]. 运筹学学报（中英文）, 2026, 30(1): 93-107.
[12]	许可, 吉兰萍, 宫华, 刘鹏, 孙文娟. 基于拍卖算法的多代理并行机生产运输协调调度[J]. 运筹学学报（中英文）, 2026, 30(1): 121-136.
[13]	王子琦, 王军霖, 徐姿. 一类非凸-非凹极小极大问题的方差缩减梯度下降上升算法[J]. 运筹学学报（中英文）, 2026, 30(1): 197-206.
[14]	杨金佶, 沈春根, 宇振盛. 关于求解平方根损失函数回归问题的自适应邻近梯度-次梯度算法的收敛性分析[J]. 运筹学学报（中英文）, 2026, 30(1): 217-234.
[15]	孙瑞卿, 张芮, 兰艳, 李伟东. 提前完工总量最大化问题的LPT算法[J]. 运筹学学报（中英文）, 2025, 29(4): 249-254.

链图的距离特征值

The distance spectra of chain graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

相关文章 15

编辑推荐

Metrics

本文评价