English

运筹学学报 >

2024 , Vol. 28 >Issue 1: 112 - 120

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.01.009

 

链图的距离特征值

展开
  • 1. 中国人民大学数学学院, 北京 100872
马梦郁 E-mail: senorita@ruc.edu.cn

收稿日期: 2020-12-25

  网络出版日期: 2024-03-16

基金资助

国家自然科学基金(11971479)

版权

运筹学学报编辑部, 2024, 版权所有，未经授权。
收起

The distance spectra of chain graphs

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

Received date: 2020-12-25

  Online published: 2024-03-16

Copyright

, 2024, All rights reserved, without authorization
Fold

摘要

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

关键词： 链图; 距离特征值; 合理划分

本文引用格式

吕雪征, 马梦郁 . 链图的距离特征值[J]. 运筹学学报, 2024 , 28(1) : 112 -120 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.009

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

参考文献

1 Aouchiche M , Hansen P . Distance spectra of graphs: A survey[J]. Linear Algebra and Its Applications, 2014, 458, 301- 384.
2 Aouchiche M , Hansen P . Distance spectra of graphs: A survey[J]. Linear Algebra and Its Applications, 2014, 458, 301- 386.
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.
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.
6 Staniczenko P , Kopp J , Allesina S . The ghost of nestedness in ecological networks[J]. Nature Communications, 2013, 4, 1391.
7 Alazemi A , Andelic M , Simic S K . Eigenvalue location for chain graphs[J]. Linear Algebra and Its Applications, 2016, 505, 194- 210.
8 Das K C , Alazemi A , Andelic M . On energy and Laplacian energy of chain graphs[J]. Discrete Applied Mathematics, 2020, 284, 391- 400.
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.
10 Lou Z , Lin H . Distance eigenvalues of a cograph and their multiplicities[J]. Linear Algebra and Its Applications, 2021, 608, 1- 12.
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.
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.
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.
Options
文章导航

/

〈 〉