具有大多重性特征值的图的刻画

摘要

让做一个简单的无向图。的邻接矩阵的特征值被称为特征值 ．在本文中，我们描述了所有的 -具有多重特征值的顶点图和 ，分别。此外，作为主要结果的一个应用，我们给出了具有四个不同特征值的非正则图族。

1.介绍

这里考虑的所有图都是简单的、无向的和连通的。让是一个具有顶点集的图 ．一个顶点的所有邻近点的集合用 ．两个相邻的顶点和是用 ．的邻接矩阵 之是实对称矩阵，然后呢 如果有一条边连接这两个顶点和 ；否则, ．的特征值被称为特征值 ，用 ．邻接矩阵的秩之叫军衔 ，写成 ．矩阵的秩也可以写成 ．一组独立的是使任何两个顶点之间没有边集合的最大独立集合中的顶点数称为独立数 ，用 ．两个顶点之间的距离和 ，用 ，这是最短路径的长度吗和 ．表示由的直径 ，然后 ．让是一个特征值的多重性的图 ．

图的特征值的多重性一直是人们关注的问题。罗林森对此作了广泛的研究[1- - - - - -8］．让是一个有序的图形用一个特征值 ．在[1，作者证明了如果 和 ，然后 与 ．这个上界被扩展到 与 （或等效， ）在[2］．图表满意 已在[5］．在[3.，4，6- - - - - -8[]，研究了某些特殊图类中图的特征值的多重性。此外,丰9]证明了当从图中移除一条路径时，特征值的多重性之间的许多关系。但是等人[10]给出了单环图和树的特征值多重性的两个上界。Wong等人[11[]改进了[]中树正特征值多重性的上界3.］．

注意[的上界1，2]对于特征值不等于0或-1的多重性建立。也就是说，特征值0和-1的多重性不容易上界。然后研究了图的特征值0和-1的多重性。在这里，我们感兴趣的是搜索特征值为-1或0的大多重性的图。一个图的特征值0的多重性称为图的零度，这是一个已经被深入研究过的问题。因此，值得注意的是具有大多重性特征值-1的图。更一般地说，本文研究具有某些大多重特征值的图，因为它们与具有少数不同特征值的图有关，而这些特征值已被深入研究(见[12- - - - - -18例如,)。

表示所有的集合 -具有多重特征值的顶点连通图通过 ．本文的主要结论如下:

定理1。让是一个有序的图形 ，然后 当且仅当是完全偶图吗与 ．

定理2。让是一个有序的图形 ，然后 当且仅当是完全三部图吗与 或图(见图1), 和 ．

2.证明

在证明定理之前1和2，我们首先提出一些已知的结果作为引理。

引理3(交错定理，[19])。对于一个实对称矩阵的订单 ，让是的主子矩阵与订单 ．然后, 在哪里是最大特征值。

让是一个对称实矩阵，其分块形式为 转置在哪里是 ．让的平均行和 ，然后 商矩阵是 ．如果行和是常数，那么我们说有公平的分割。

引理4(参见[19])。让是具有公平分割和的对称实矩阵的商矩阵 ．的每个特征值一个特征值是什么 ．

引理5(参见[20.，21])。让那就做个图表吧 当且仅当是完全二部图，和 当且仅当是一个完全三部图。

引理6(参见[2])。让是一个有序的图形和是多重特征值 ．如果 ，然后 或者说, 与 ．

引理7。让成为一个图表顶点, 引入小集团这样 ，那么−1是的一个特征值至少具有多重性 ．

证明。自从 诱导一个小集团和 ，然后第一个矩阵的行数 是相同的,是单位矩阵。因此 包含至少作为多重性的特征值 ，这表明一个特征值是什么至少具有多重性 ．

下面，我们给出定理的证明1和2．

2.1。定理的证明1

让是一个有序的图形 ．如果是完全偶图吗与 ，那么很容易知道的所有特征值是 与多样性 ，分别。因此, ．

现在假设 ．我们会讲到必须是一个完整的二角形图形。让是的特征值与多样性 ．首先，假设 ，然后排名之等于2，因此，完全二部图是引理中的吗5．接下来,假设 (这种情况不能从下面的证据发生)。然后, 与作为单位矩阵，其中表示独立数 (否则, 显然,一个矛盾)。此外，我们声称是一个图表，也就是说，不包含路径作为一个诱导子图。否则,假设包含作为一个诱导子图，然后，（resp。， ）的主子矩阵是（resp。， ）.因此，人们可以获得这一点 一个矛盾。作为一个结果, ．如果 ， 是完全图的特征值和具有多重性1和 ，分别。很明显, ．假设 和是阶为的任意连通子图吗在下面。的特征值之和之 ，它来自引理3.那

自从 ，我们获得还包含作为多重性至少为2的特征值。回忆, ， ，和那么，这是图表吗必须同其中一个图同构吗 (见图2）.然而，通过直接计算， 从表中不包含至少2的多重性非零特征值1,一个矛盾。

这样，证明就完成了。

2.2。定理的证明2

让是一个有序的图形 ．我们首先说明充分性部分。如果是完全三部图吗与 ，然后从引理5，很明显 具有多重特征值0 ．假设是图与 和 在图1．从引理7，至少包含−1作为多重特征值 ．根据分区 ，系数矩阵之是

通过计算，得到矩阵的行列式 是 这意味着- 1不是商矩阵的特征值 ．应用引理4，我们得到−1是的一个特征值与多样性 ；也就是说, ．

现在我们来证明必要性部分。假设 和特征值是什么与多样性 ．首先,如果 ，然后 和是一个完整的三方图与 从引理5．接下来,假设 ，然后 ．我们声称独立数 ．相反地假设 ．如果 ， 是完全图和 从定理的证明1．假设 与 一组独立的 ，,让是的主子矩阵被 ．然后, 矛盾与 ．

现在假设 与 的最大独立集 ，哪个会产生每个顶点至少与其中一个相邻 ．为了完成证明，以下声明是必要的。

权利要求1。特征值 ．
回忆, ，此外,如果 ，然后从引理6和 ， 矛盾与 ．因此， ．

要求2。不存在与 ．
不失一般性，假设存在一个顶点的矛盾这样 ， 和 ．让是的主子矩阵被 ，然后的主子矩阵是和

表示由的行按顶点索引 ．自从 ，很清楚 是线性无关的，这就产生了其他的行可以写成线性组合吗 ．让

应用(11的第一、第二和第四列 ，我们得到了 收益率, ，矛盾与索赔1．

要求3。不存在与每个相邻的顶点 ．

假设存在一个矛盾点这样 ．与索赔证明类似2,让是的主子矩阵被 ，然后

作为 ，那么显然 是线性无关的，哪个张成的行空间 ．让

应用(14)到列 ，我们得到了 这意味着 ，矛盾与索赔1．综合以上观点，我们发现如果 ，然后不相连，就是矛盾。作为一个结果, ．回顾之前的讨论，可以证明 ．

接下来，我们证明不包含诱导路径 ，也就是说,是一个cograph。如果包含作为一个诱导子图，则考虑一个5阶的诱导子图 ，我们可以看到,必须包含一些 (见图3.)作为一个诱导子图(注意 ）.应用引理3.和索赔1，我们得到 包含作为多重性至少为2的特征值。但是，通过直接计算，可以得出−1的多重性作为的特征值 不多于一个(见表2),一个矛盾。因此,是图和直径吗 ．

现在我们可以完成证明了。请注意, 和 从上面的过程。让 直径为 ，然后 最大独立集是什么每一个顶点 至少与其中一个相邻 ．让 然后是外面的任何顶点正好属于其中之一 ．我们需要以下索赔。

要求4。每个顶点的（resp。， ）与每个人相邻 ．

假设 和 这样 ．然后,顶点 诱导路径 ，一个矛盾。的证明是平行的,省略了。

要求5。所有的顶点（resp。， ）诱导小集团 ．

我们只证明了 ．如果 和 ，然后 诱使一个独立的一套 ，矛盾与 ．

要求6。所有的顶点诱导小集团 ．

假设 和 ．考虑一个诱导子图第5阶 ，我们获得是同构的吗 (见图4）.它来自引理3.那包含作为多重性至少为2的特征值。但 表中不包含重数2的特征值3.,一个矛盾。

从索赔4- - - - - -6和事实 和 ，我们得出,是同图的吗在图1,如需要。证明完成了。

范•达姆(14)和黄和黄[18]研究了具有四个不同特征值的正则图。这里，作为定理的一个应用2，我们得到了一个具有四个不同特征值的非正则图族。

推论8。这个图与 和 (见图1)包含四个不同的特征值，这不是一个正则图。

证明。从定理的证明2，我们看到- 1是的一个特征值与多样性剩下的三个特征值这些是商矩阵吗之 ．自从 ，然后 包含两个正特征值和一个负特征值。根据Perron-Frobenius定理，的最大特征值很简单;的最大特征值（resp。， ）很简单。因此, 包含三个不同的特征值，即包含三个不同的特征值。−1不是的特征值 ，然后包含四个不同的特征值。此外，很明显不是正则图。

数据可用性

在本研究中，我们使用理论模型的方法来进行我们的研究。通过理论推导和数值研究，初步得出了结论。其中，数值研究数据来源于作者的假设，也在表格中说明1- - - - - -3.．因此，我们声明没有进一步的外部数据用于支持这项研究。

利益冲突

作者声明他们没有利益冲突。

致谢

国家自然科学基金资助项目(no . 11771443, no . 71902105);浙江省教育厅访问学者与教师发展项目(no . FX2018113)。关键词:岩石力学，岩石力学，岩石力学，岩石力学

参考

1. P. Rowlinson， <多重特征值的图>线性代数及其应用(第283卷，第283期)1-3，页75-85,1998。视图:出版商的网站|谷歌学术搜索
2. F. K. Bell和P. Rowlinson，“关于图特征值的多重性”，伦敦数学学会简报第35卷，没有。3，页401-408,2003。视图:出版商的网站|谷歌学术搜索
3. 罗林森，《论树的多重特征值》，线性代数及其应用(第432卷，第4期)11，第3007-3011页，2010。视图:出版商的网站|谷歌学术搜索
4. 罗林森，“论图的特征值多重性与周长”，线性代数及其应用(第435卷第40期)10，页2375-2381,2011。视图:出版商的网站|谷歌学术搜索
5. P. Rowlinson，“关于具有极大多重特征值的图”，离散数学第313卷第313号11, pp. 1162-1166, 2013。视图:出版商的网站|谷歌学术搜索
6. P. Rowlinson，“三次图的特征值多重性”，线性代数及其应用，第444卷，211-218页，2014。视图:出版商的网站|谷歌学术搜索
7. J. Capaverde和P. Rowlinson，“四次图的特征值多重性”，线性代数及其应用，第535卷，第160-170页，2017。视图:出版商的网站|谷歌学术搜索
8. P. Rowlinson，“正则图的特征值多重性”，离散应用数学， vol. 269, pp. 11-17, 2019。视图:出版商的网站|谷歌学术搜索
9. da Fonseca，“一个图的特征值的多重性的注释”，线性与多重线性代数第53卷，第2期。4，页303-307,2006。视图:出版商的网站|谷歌学术搜索
10. “图特征值多重性的一个注记”，中国科学(d辑:数学)，vol . 33, no . 1, no . 3，线性代数及其应用，第442卷，第69-74页，2014。视图:出版商的网站|谷歌学术搜索
11. d . Wong问:周,f .田”的多样性特征值的树木,线性代数及其应用，第593卷，第180-187页，2020年。视图:出版商的网站|谷歌学术搜索
12. M. Doob，“具有少量不同特征值的图”，纽约科学院年鉴第175卷，没有。1, 104-110页，1970。视图:出版商的网站|谷歌学术搜索
13. E. R. van Dam，“具有三个特征值的非正则图”，组合理论学报，B辑，第73卷，第2期。2，第101-118页，1998。视图:出版商的网站|谷歌学术搜索
14. E. R. van Dam，“具有四个特征值的正则图”线性代数及其应用，第226-228页，139-162页，1995。视图:出版商的网站|谷歌学术搜索
15. M. Muzychuk和M. Klin，“关于具有三个特征值的图”，离散数学第189卷第2期1-3，页191-207,1998。视图:出版商的网站|谷歌学术搜索
16. P. Rowlinson， "关于只有三个不同特征值的图"线性代数及其应用，第462-473页，2016年。视图:出版商的网站|谷歌学术搜索
17. 郑晓明，G. R. W. Greaves, J. H. Koolen，“三特征值和第二大特征值不大于1的图”，《计算机科学与技术》，2010年第1期组合理论学报，B辑， vol. 129, pp. 55-78, 2018。视图:出版商的网站|谷歌学术搜索
18. X. Huang和Q. Huang，“关于具有四个特征值的正则图”，线性代数及其应用， vol. 512, pp. 219-233, 2017。视图:出版商的网站|谷歌学术搜索
19. A. E.布劳威尔和W. H.海默斯，光谱图，施普林格，纽约，美国，2012。视图:出版商的网站
20. I. Sciriha，《在图表的排列上组合学，图论与算法2Y. Alavi, D. R. Lick和A. Schwenk, Eds。，pp. 769–778, University of Malta, Michigan, 1999.视图:谷歌学术搜索
21. B. Cheng和B. Liu，“关于图的零度性”，线性代数电子杂志，第16卷，60-67页，2007。视图:出版商的网站|谷歌学术搜索

版权

祁林明等人版权所有这是一篇开放获取的文章知识共享署名许可，允许在任何媒介上不受限制地使用、分发和复制，只要原稿被适当引用。