链图的距离特征值

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

参考文献 16

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]. 运筹学学报, 2024, 28(1): 89-100.
[2]	李颖涵, 童小娇, 杨柳. 基于矩不确定模糊集的分布鲁棒风险-回报优化模型研究[J]. 运筹学学报, 2024, 28(1): 77-88.
[3]	徐洋, 王军霖, 徐姿. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法[J]. 运筹学学报, 2024, 28(1): 18-28.
[4]	孟辛晴, 张文星. 求解一类线性等式约束凸优化问题的加速方法[J]. 运筹学学报, 2024, 28(1): 1-17.
[5]	王晓. 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023, 27(4): 153-165.
[6]	王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述[J]. 运筹学学报, 2023, 27(4): 106-135.
[7]	刘永鸿, 韩丛英, 郭田德. 基于深度学习的指纹方向场提取算法[J]. 运筹学学报, 2023, 27(4): 1-19.
[8]	张莹, 敬新奇, 王长军. 一个双拟阵下的最优定价存在性猜想[J]. 运筹学学报, 2023, 27(4): 166-174.
[9]	姜波. 非负正交约束优化问题的理论、算法及应用[J]. 运筹学学报, 2023, 27(4): 136-152.
[10]	邵梦真, 余长君. 最优控制问题的直接法综述[J]. 运筹学学报, 2023, 27(4): 81-105.
[11]	艾文宝, 梁炜, 张梦晓. S-引理及其进展[J]. 运筹学学报, 2023, 27(4): 20-32.
[12]	曾静, 丁若文. 一类带映射差的非凸向量优化问题解的稳定性[J]. 运筹学学报, 2023, 27(3): 121-128.
[13]	张昀蔚, 韩曙光. 收送货同时的城市无人物流配送问题研究[J]. 运筹学学报, 2023, 27(3): 53-67.
[14]	苏珂, 任晓慧. 需求不确定的修正库存定价模型[J]. 运筹学学报, 2023, 27(3): 21-36.
[15]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.

链图的距离特征值

The distance spectra of chain graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 16

相关文章 15

编辑推荐

Metrics

本文评价