链图的距离特征值

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2024.01.009

https://www.ort.shu.edu.cn/EN/Y2024/V28/I1/112

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]	WANG Xiangfeng, ZENG Shangzhi, ZHANG Jin, ZHOU Jinchuan. Proximal-based methods can guarantee blunt local minimizer for nonconvex nonsmooth optimization problem [J]. Operations Research Transactions, 2026, 30(2): 1-23.
[2]	MEN Yanchao, LI Xudong. Fast algorithm for OWL1 norm constrained regression model [J]. Operations Research Transactions, 2026, 30(2): 24-44.
[3]	ZENG Jing, XIANG Yao, ZHANG Wenyan. The well-posedness of traffic equilibrium problems [J]. Operations Research Transactions, 2026, 30(2): 58-68.
[4]	WANG Feng, HANG Bo, HUANG Jinzhou, XU Degang, ZHANG Zeyu, LIU Jiamou. Research of touring route planning based on spatio-temporal awareness [J]. Operations Research Transactions, 2026, 30(2): 69-78.
[5]	WU Xiaoyu, SHAO Hu, LIU Pengjie, ZHOU Jincheng. Two RMIL-type conjugate gradient methods with sufficient descent property and applications in image restoration [J]. Operations Research Transactions, 2026, 30(2): 79-92.
[6]	CUI Hengxin, JIANG Fan. Inexact proximal point algorithms and projection methods for monotone variational inequalities [J]. Operations Research Transactions, 2026, 30(2): 194-208.
[7]	ZHANG Xuefeng, PENG Xiao, CHEN Liangyu, YANG Zhengfeng, ZENG Zhenbing. A review of intelligent branch and bound algorithms for mixed integer linear programming problems [J]. Operations Research Transactions, 2026, 30(2): 237-270.
[8]	WEI Jiazhen, BIAN Wei. A survey on research advances in consensus-based optimization algorithm [J]. Operations Research Transactions, 2026, 30(1): 1-23.
[9]	ZHOU Yunxu, YAO Fanjun, GAO Hongwei. Blockchain empowering the digital transformation: Study on the coordination strategies of supply chain [J]. Operations Research Transactions, 2026, 30(1): 61-74.
[10]	ZHAO Hongxin, KONG Lingchen. Research on diversification portfolio optimization model and method [J]. Operations Research Transactions, 2026, 30(1): 75-92.
[11]	SUN Ke, WANG Jinting, WANG Zhongbin. The economics of waiting-area entertainment [J]. Operations Research Transactions, 2026, 30(1): 93-107.
[12]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[13]	WANG Ziqi, WANG Junlin, XU Zi. A variance reduced gradient descent ascent algorithm for a class of nonconvex-nonconcave minimax problems [J]. Operations Research Transactions, 2026, 30(1): 197-206.
[14]	YANG Jinji, SHEN Chungen, YU Zhensheng. Convergence analysis of an adaptive proximal gradient-subgradient algorithm for square-root-loss regression problems [J]. Operations Research Transactions, 2026, 30(1): 217-234.
[15]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.

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