链图的距离特征值

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

Abstract

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

CLC Number:

O221.2

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

Figures/Tables 2

References 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]	CHENG Yukun, HAN Xin, CHEN Xiuyang, ZHANG Zhao. Survey on several combinatorial optimization games on networks [J]. Operations Research Transactions, 2024, 28(2): 1-29.
[2]	ZHANG Jiaqi, LI Jueyou. A class of differential privacy stochastic gradient descent algorithm with adaptive gradient clipping [J]. Operations Research Transactions, 2024, 28(2): 47-57.
[3]	XU Juannian, MA Ran, HAN Wenwen, ZHANG Yuzhong. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[4]	YE Minglu, HUANG Ming. An inertial projection algorithm for nonmonotone continuous variational inequalities [J]. Operations Research Transactions, 2024, 28(2): 81-92.
[5]	WANG Fusheng, SHI Luyu. An accelerated proximal stochastic gradient method with variance reduction based on Polyak step size [J]. Operations Research Transactions, 2024, 28(2): 131-142.
[6]	Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints [J]. Operations Research Transactions, 2024, 28(1): 89-100.
[7]	Yinghan LI, Xiaojiao TONG, Liu YANG. The study of distributionally robust reward-risk optimization models with moment-based ambiguity set [J]. Operations Research Transactions, 2024, 28(1): 77-88.
[8]	Yang XU, Junlin WANG, Zi XU. A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems [J]. Operations Research Transactions, 2024, 28(1): 18-28.
[9]	Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization [J]. Operations Research Transactions, 2024, 28(1): 1-17.
[10]	Xiao WANG. Stochastic approximation methods for nonconvex constrained optimization [J]. Operations Research Transactions, 2023, 27(4): 153-165.
[11]	Xiangfeng WANG, Wenhao LI. Machine learning-driven multi-agent pathfinding: An overview [J]. Operations Research Transactions, 2023, 27(4): 106-135.
[12]	Yonghong LIU, Congying HAN, Tiande GUO. Fingerprint orientation field estimation algorithm based on deep learning [J]. Operations Research Transactions, 2023, 27(4): 1-19.
[13]	Ying ZHANG, Xinqi JING, Changjun WANG. A conjecture of optimal pricing for two matroids [J]. Operations Research Transactions, 2023, 27(4): 166-174.
[14]	Bo JIANG. On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints [J]. Operations Research Transactions, 2023, 27(4): 136-152.
[15]	Mengzhen SHAO, Changjun YU. A survey of direct methods for optimal control problems [J]. Operations Research Transactions, 2023, 27(4): 81-105.

The distance spectra of chain graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 16

Related Articles 15

Recommended Articles

Metrics

Comments