一类树的主特征值数目刻画
Characterization of the Number of Main Eigenvalues of a Class of Trees

作者: 杜泽楠 , 于 倩 :长安大学,理学院,陕西 西安;

关键词: 邻接矩阵主特征值树图Adjacency Matrix Main Eigenvalues Tree

摘要: 一个图的邻接矩阵的特征值称为图的特征值,图的所有特征值的多重集称为图的谱。如果图的一个特征值所对应的特征空间与全1向量不正交,则称其为主特征值,主特征值对于刻画图及研究图的性质都有重要的意义。刻画恰有k(2≤k≤n)个主特征值的图是一个存在已久的问题,本文给出了一类树的主特征值数目的下界。

Abstract: The eigenvalues of the adjacency matrix of a graph are called the eigenvalues of a graph, the multi-set of all eigenvalues of a graph is called the spectrum of a graph. An eigenvalue of a graph is a main eigenvalue if its eigenspace is not orthogonal to the all-ones vector, the main eigenvalues are significant to the characterization of graphs and the properties of graphs. Characterizing graphs with k(2≤k≤n) number of main eigenvalues are a long-standing problem. In this paper, the lower bound of main eigenvalues of a class of trees is determined.

1. 引言

图论起源于18世纪哥尼斯堡七桥问题,瑞士数学家Leonhard Euler在1736年发表了一篇解决七桥问题的论文,该论文被认为是图论的第一篇论文,Euler因此也被誉为图论之父。1936年匈牙利数学家König出版了第一本图论专著《Theory of Directed and Undirected Graphs》,标志着图论正式成为一门独立的学科。作为离散数学重要的分支之一,图论已发展成一门独立的学科,它主要研究某一集合元素间可用拓扑图形表示的二元关系。根据研究方法和内容的不同,图论已衍生出许多分支,如拓扑图论、代数图论、随机图论、结构图论、模糊图论、极值图论、超图论等。图谱理论作为代数图论中的一个重要分支,与群论、矩阵论、组合数学、多项式理论、线性代数等学科都有着密切的联系,它主要研究图的组合性质和图相关矩阵(如邻接矩阵,拉普拉斯矩阵,无符号拉普拉斯矩阵,距离矩阵)的代数性质之间的关系。

一个图的邻接矩阵的特征值称为图的特征值,图的所有特征值的多重集称为图的谱。1978年Cvetković D. [1] 第一次提出了图的主特征值的概念。若图的邻接矩阵A的特征值 λ 存在一个特征向量x,满足x与元素全为1的向量e不正交,即 e T x 0 ,那么就称 λ 为图的一个主特征值。Cvetković D.在文献 [1] 中提出问题,如何刻画恰有 k ( 2 k n ) 个主特征值的图。对于一个连通图G,因为其邻接矩阵是不可约的,故由著名的Perron-Frobenius定理可知G的最大特征值为主特征值。更一般的,恰有一个主特征值的图为正则图 [1]。已经有一系列论文对于恰有两个主特征值的图进行了刻画,如Cardoso [2],Hagos [3], Hayat [4],Hou et al. [5] [6] [7],Lepović [8],Shi [9] 等,然而这项工作还远未完成。2012年Godsil C. [10] 猜想:几乎所有图的全部特征值均为主特征值,2016年O’Rourke [11] 证明了这个猜想的正确性,该结论说明主特征值对于刻画图及研究图的性质都有重要的意义。

2. 预备知识

定义2.1 [12] 对于n个顶点的图,其邻接矩阵定义为 A = ( a i j ) n × n ,其中 a i j = { 1 , v i v j 0

由上述定义可知邻接矩阵为实对称矩阵且主对角元素为0。

定义2.2 [12] 路图 P n 表示从一个顶点 v 1 出发,依次将新点 v i v i 1 ( i n ) 相连所得到的图。

定理2.3 [13] 路图 P n 的特征多项式为 φ 0 ( x ) = 1 φ 1 ( x ) = x φ n ( x ) = x φ n 1 ( x ) φ n 2 ( x ) ( n 2 )

推论2.4 当 n = 2 k 时, φ n ( x ) 为偶函数;当 n = 2 k + 1 时, φ n ( x ) 为奇函数。

证明: k = 0 时结论显然成立,

k = 1 时, φ 2 ( x ) = x φ 1 ( x ) φ 0 ( x ) = x φ 1 ( x ) φ 0 ( x ) = φ 2 ( x )

φ 3 ( x ) = x φ 2 ( x ) φ 1 ( x ) = x φ 2 ( x ) + φ 1 ( x ) = φ 3 ( x ) ,成立。

k = 2 时, φ 4 ( x ) = x φ 3 ( x ) φ 2 ( x ) = x φ 3 ( x ) φ 2 ( x ) = φ 4 ( x )

φ 5 ( x ) = x φ 4 ( x ) φ 3 ( x ) = x φ 4 ( x ) + φ 3 ( x ) = φ 5 ( x ) ,成立。

以此类推,n为奇偶的情况可交替证明,故结论成立。

定义2.5 [14] 星形树 S ( n 1 , n 2 , n 3 , , n k ) 表示将一个顶点 v 分别与路 P n 1 , , P n k 的一端相连所构成的图,见图1

Figure 1. S ( n 1 , n 2 , n 3 , , n k )

图1. S ( n 1 , n 2 , n 3 , , n k )

定理2.6 [14] 对于正整数m,星形树 S ( 1 , 1 , m ) 的特征值为:

S p e c ( S ( 1 , 1 , m ) ) = { 2 cos ( 2 k + 1 2 m + 4 π ) : k = 0 , 1 , , m + 1 } { 0 }

定义2.7 [12] 若图G的顶点集可划分为两个非空子集X和Y,使得图G的任一条边都有一个端点在X中,另一个端点在Y中,则称图G为二部图。

推论2.8 [12] 若图G为二部图,顶点集可划分为X和Y,其中它们的阶数分别s和t,则其全部特征值关于原点对称。进一步若特征值 λ 对应特征向量 x = ( x 1 , , x s , y 1 , , y t ) T ,则 λ 对应特征向量 x = ( x 1 , , x s , y 1 , , y t ) T

3. 一类星形树的主特征值数目

定理3.1 星形树 S ( 1 , 1 , m ) ( m 1 ) 的主特征值数目有以下情况:当m为偶数时, S ( 1 , 1 , m ) 的主特征值数大于等于 m 2 + 1 ,其中0是单根且为非主特征值;当m为奇数时,非零特征值 ± λ 同为主特征值或同为非主特征值,且0是二重根,进一步当 m = 4 k 3 时,0为非主特征值;当 m = 4 k 1 时,0为主特征值 ( k 1 )

证明:首先分析图 S ( 1 , 1 , m ) 根的情况,因为 λ = { 0 } { 2 cos ( 2 k + 1 2 m + 4 π ) , k = 0 , 1 , , m + 1 } ,而 2 k + 1 2 m + 4 = 1 2 当且仅当 k = m + 1 2 ,说明只有m为奇数即 | V ( S ( 1 , 1 , m ) ) | = m + 3 为偶数时,0是 S ( 1 , 1 , m ) 的二重根,m为偶数时0为单根。因为余弦值 cos θ 在区间 [ 0 , π ] 上单调递减,故图 S ( 1 , 1 , m ) 的非零特征值均为单根,且关于原点对称。

设图 S ( 1 , 1 , m ) 的邻接矩阵为 A = ( 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 ) n × n ,易见 n = m + 3 。对其特征值 λ 及对应特征向量x有 A x = λ x ,令 x = ( x 1 , x 2 , , x n ) T ,展开方程得到:

{ x 3 = λ x 1 x 3 = λ x 2 x 1 + x 2 + x 4 = λ x 3 x 3 + x 5 = λ x 4 x 4 + x 6 = λ x 5 x n 2 + x n = λ x n 1 x n 1 = λ x n (1)

由(1)式可知,A的每一个特征向量x都可以由最后一个分量 x n ( 0 ) 表示,不妨设 x n = 1

x n = 0 ,则代入(1)式可得:

{ x 1 + x 2 = 0 x n = x n 1 = x n 2 = x n 3 = = x 5 = x 4 = x 3 = 0

故易见向量 x = ( 1 , 1 , 0 , , 0 ) T 是对应特征值0的特征向量,即满足 A x = 0 x ,由 e T x = 0 知0是非主特征值,且该0特征值不由 2 cos ( 2 k + 1 2 m + 4 π ) 贡献。

将(1)式左右两端相加得:

2 i = 1 n x i x 1 x 2 + x 3 x n = λ i = 1 n x i

化简得:

( 2 λ ) i = 1 n x i = x 1 + x 2 x 3 + x n

因为 λ ( 2 , 2 ) 2 λ > 0 ,故 i = 1 n x i = 0 λ 为非主特征值当且仅当

x 1 + x 2 x 3 + x n = 0 (2)

下面讨论 λ 0 的情况。

此时显然 x 1 0 ,否则有 x n = x n 1 = x n 2 = x n 3 = = x 5 = x 4 = x 3 = x 2 = x 1 = 0 ,向量x无意义。

由(1)式知 x n 0 时,有 x 1 = x 2 ,故(2)式可表示为:

( 2 λ ) x 1 + 1 = 0 (3)

因为 2 λ > 0 ,故当 x 1 > 0 时(3)式左端恒大于零,等式矛盾,说明 x 1 > 0 i = 1 n x i 0 ,对应特征值 λ 为主特征值。

1) 当 m 为偶数时, n = m + 3 为奇数,对于特征值 ± λ ,若对应 λ 的特征向量为 x = ( x 1 , x 2 , , x n 1 , 1 ) T ,因为 S ( 1 , 1 , m ) 为二部图,连接在中心点 v 的两个一度点和 P m 中与 v 的距离为奇数的顶点可划分为一个顶点集,则由推论2.8可得对应 λ 的特征向量为 y = ( x 1 , x 2 , x 3 , x 4 , x 5 , , x n 2 , x n 1 , 1 ) T x y 的第一个分量异号且不等于0,则 ± λ 至少有一个为主特征值,这就说明对于奇数个顶点的图 S ( 1 , 1 , m ) ,其至少有 m + 3 1 2 个主特征值。

2) 当 m 为奇数时, n = m + 3 为偶数,对于特征值 ± λ ,若对应 λ 的特征向量为 x = ( x 1 , x 2 , , x n 1 , 1 ) T ,同理可得对应 λ 的特征向量为 y = ( x 1 , x 2 , x 3 , x 4 , x 5 , , x n 2 , x n 1 , 1 ) T x y 的第一个分量同号且不等于0,说明对于偶数个顶点的图 S ( 1 , 1 , m ) ,其特征值 ± λ 同为主特征值(或非主特征值)。

最后讨论0作为二重根出现的情况。

由上面分析可知当 m 为奇数,0是二重根,且其中一个0对应特征向量 x = ( 1 , 1 , 0 , , 0 ) T

x n = 1 代入(1)式并化简得:

{ x 3 = λ x 4 x 5 x 4 = λ x 5 x 6 x n 2 = λ x n 1 x n x n 1 = λ x n = 1

观察可得向量 x = ( x 1 , x 2 , , x n ) T 的分量满足递推关系 x t = λ x t + 1 x t + 2 ( t = 3 , 4 , , n 2 ) ,且初始值 x n = 1 x n 1 = λ 。则对比路 P n 的特征多项式可得:

{ φ n 3 ( λ ) = x 3 φ n 4 ( λ ) = x 4 φ 2 ( λ ) = x n 2 φ 1 ( λ ) = x n 1 φ 0 ( λ ) = x n

故由 x 1 + x 2 + x 4 = λ x 3 可得:

x 1 + x 2 = λ x 3 x 4 x 1 + x 2 = λ φ n 3 ( λ ) φ n 4 ( λ ) = φ n 2 ( λ )

代入(2)式有 φ n 2 ( λ ) + 1 = 0 (此时 x 3 = λ x 1 = 0 )。

φ n ( x ) 的奇偶性可得,

φ 0 ( 0 ) = 1 , φ 1 ( 0 ) = 0 , φ 2 ( 0 ) = 1 , φ 3 ( 0 ) = 0 , φ 4 ( 0 ) = 1 , , φ 4 t ( 0 ) = 1 , φ 4 t + 2 ( 0 ) = 1 , ( t = 0 , 1 , )

故当 n = 4 k + 2 时, φ 4 k + 2 2 ( 0 ) + 1 = 2 > 0 0 为主特征值;当 n = 4 k 时, φ 4 k 2 ( 0 ) + 1 = 1 + 1 = 0 0 为非主特征值,其中 k 1

定义3.2 [1] 对于一个图 G ,若其顶点集可划分为 V ( G ) = V 1 V 2 V k V i V i 为空集,其中 V i 中的每个顶点在 V j 中的邻点个数相同,记为 b i j i , j { 1 , 2 , , k } ,则称该划分为图G的一个公平划分,记为 Π 。以 V 1 , V 2 , , V k 为顶点集, V i V j b i j 条弧的有向多重图称为图G的商图,矩阵 B = ( b i j ) k × k 称为商矩阵。

定理3.3 [1] 对于图G的任意商图H,H的谱包含G的全部主特征值。

对于任意图G的一个公平划分 Π 来说,因为每个划分 V i 内的顶点处于G自同构群中的同一轨道,故由定理3.3可知,对于恰有k个主特征值的图,其自同构群至少有k条轨道。

推论3.4 星形树 S ( m 1 , , m 1 , m 2 , , m 2 , , m s , , m s ) 至多有 m 1 + m 2 + + m s + 1 个主特征值,其中 m 1 , , m s 的个数分别为 t 1 , , t s ( t i 1 )

证明:显然星形树 S ( m 1 , , m 1 , m 2 , , m 2 , , m s , , m s ) 的顶点数为 t 1 m 1 + t 2 m 2 + + t s m s + 1 ,我们可以找到其阶数最小的商图H,点集划分如下:首先将长度相同的 P m i 分为一组,其中每条路 P m i 中与中心点 v 距离相同的点处于同一轨道,故可将同一轨道中的 t i 个顶点划分为一个顶点集,因此对每组 P m i 来说,其可划分为因子图H中的 m i 个顶点。同理每组 P m i 均可划分为H中的 m i 个顶点,又中心点 v 自处一个轨道,故H的阶为 m 1 + m 2 + + m s + 1 。由定理3.3知,任意商图的谱包含原图的全部主特征值,故星形树 S ( m 1 , , m 1 , m 2 , , m 2 , , m s , , m s ) 至多有 m 1 + m 2 + + m s + 1 个主特征值。

参考文献

文章引用: 杜泽楠 , 于 倩 (2021) 一类树的主特征值数目刻画。 运筹与模糊学, 11, 131-136. doi: 10.12677/ORF.2021.112016

参考文献

[1] Cvetković, D. (1978) The Main Part of the Spectrum, Divisors and Switching of Graphs. Publications de l’Institut Mathématique (Beograd), 23, 31-38.

[2] Butler, G. and McKay, J. (1983) The Transitive Groups of Degree up to Eleven. Communications in Algebra, 11, 836-911.
https://doi.org/10.1080/00927878308822884

[3] Hagos, E.M. (2002) Some Results on Graph Spectra. Linear Algebra and Its Applications, 356, 103-111.
https://doi.org/10.1016/S0024-3795(02)00324-5

[4] Hayat, S., Koolen, J.H., Liu, F. and Qiao, Z. (2016) A Note on Graphs with Exactly Two Main Eigenvalues. Linear Algebra and Its Applications, 511, 318-327.
https://doi.org/10.1016/j.laa.2016.09.019

[5] Hou, Y.P., Tang, Z.K. and Shiu, W.C. (2012) Some Results on Graphs with Exactly Two Main Eigenvalues. Applied Mathematics Letters, 25, 1274-1278.
https://doi.org/10.1016/j.aml.2011.11.025

[6] Hou, Y.P. and Tian, F. (2006) Unicyclic Graphs with Exactly Two Main Eigenvalues. Applied Mathematics Letters, 19, 1143-1147.
https://doi.org/10.1016/j.aml.2005.11.025

[7] Hou, Y.P. and Zhou, H.Q. (2005) Trees with Exactly Two Main Eigenvalues. Journal of Natural Science of Hunan Normal University, 26, 1-3. (In Chinese)

[8] Lepović, M. (2001) Some Results on Graphs with Exactly Two Main Eigenvalues. Publikacija Elektrotehnikog Fakulteta Serija Matematika, 12, 68-84.

[9] Shi, L. (2009) On Graphs with Given Main Eigenvalues. Applied Mathematics Letters, 22, 1870-1874.
https://doi.org/10.1016/j.aml.2009.06.027

[10] Godsil, C. (2012) Controllable Subsets in Graphs. Annals of Com-binatorics, 16, 733-744.
https://doi.org/10.1007/s00026-012-0156-3

[11] O’Rourke, S. and Touri, B. (2016) On a Conjecture of Godsil Concerning Controllable Random Graphs. SIAM Journal on Control and Optimization, 54, 3347-3378.
https://doi.org/10.1137/15M1049622

[12] 高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009.

[13] Biggs, N. Algebraic Graph Theory [M]. 北京: 世界图书出版公司, 2004.

[14] Oboudi, R.M. (2018) On the Eigenvalues and Spectral Radius of Starlike Trees. Aequationes Mathematicae, 92, 683-694.
https://doi.org/10.1007/s00010-017-0533-4

分享
Top