1. 引言
在本文中,我们考虑的图都是简单无向有限图。设是顶点集,边集的图。我们称矩阵为图的邻接矩阵,其中等于顶点与顶点的边数。显然,邻接矩阵是一个实对称非负矩阵。邻接矩阵的特征值称为图的特征值。如果一个向量中的所有分量都是非零的,那么称这个向量是无零元素的向量。若图的特征值所对应的特征空间与全为1的向量不正交,那么称是图的主特征值。图的主特征值由Cvetković [1] 在1978年引入,最初是用来简化计算图中长度为的不同游走数(walk)的问题,并且作者还提出如何刻画具有个主特征值的图的问题。在文献 [2] [3] 中,Hou等人刻画了恰好具有两个主特征值的单圈图、双圈图和三圈图。Huang等人在文献 [4] 中给出了构造具有k个主特征值的连通图的方法。Du等人在文献 [5] 中通过图的并、连接等操作构造了顶点为n的无穷多个具有个主特征值的图。图的主特征值在许多领域中都有重要的应用。在代数图论中,可以通过图的主特征值来研究图的其它不变量,例如图的主角与主特征值的对应关系;在群理论中,Cvetković和Fowler [6] 给出了图的主特征值的个数就是图的自同构群作用在它的顶点集上的轨道数的下界;在量子化学中,Cvetković和Gutman [7] 利用图的主特征值为研究简单Hückel模型提供了关于π轨道的形式及其相对能量的信息,Hückel分子轨道的Hamilton算子的主特征值是分子的电子轨道能级,主特征向量决定分子的电子轨道。
符号图是一个有序二元组,其中底图,符号函数。当符号函数在符号图的所有边上对应为正号时,我们称为全正的符号图。我们称为符号图的邻接矩阵,其中当顶点与顶点之间的边为正号时,;当顶点与顶点之间为负号时,;当顶点与顶点之间没有边时,。设是的一个特征值,如果存在属于的一个特征向量,使得,则称是的一个主特征值。设v是符号图的任意顶点,X是符号图顶点集的任意子集,在符号图中切换v是指改变与v相邻的边的符号,切换X是指切换子集X里的所有点。给定符号图的顶点集的某个子集X,设,其中当时,当时,称S为符号图关于X的切换矩阵。显然,在符号图的顶点子集X处做切换后会得到新的符号图,且。也就是说,如果是的特征值,u是对应的一个特征向量,那么也是的特征值,Su是在中对应的一个特征向量。本文主要考虑可以通过全正符号图做切换得到的符号图。近几年来,许多关于图的主特征值的结论被推广到符号图中,例如在G图中,具有一个主特征值的图当且仅当它是正则图 [1] ,然而在符号图中,具有一个主特征值的符号图当且仅当它是网正则图 [8] 等。Akbari等人在文献 [9] 中提出一个猜想:除了和之外,任意全正的符号图都存在一个切换使得切换之后的符号图的所有特征值都是主特征值。目前,已经证明了Cayley图,距离正则图、顶点传递图、边传递图、双星图、路径、完全多部图、调和树、一类特殊树对该猜想成立 [1] [10] 。
设,其中p是一个素数,e是任意正整数。对于,设P和L是有限域上维向量空间的两个副本(copy),我们称P里面的元素为点(point),记作;L里面的元素称为线(line),记作。Wenger图,记为,是以P和L为顶点集的二部图,任意的点和线相邻当且仅当以下m个方程成立:
(1)
注意,Wenger图有个顶点,条边,而且它是q-正则图。Wenger图最早由Wenger在1991年引入,最初用来解决极值图论问题 [11] 。Wenger图的另外一种表示由Viglione提出 [12] ,他将定义方程组的等式右端仅用关于和的单项式表示,即,其中。Lazebnik和Ustimenko在文献 [13] 中表明温格尔图的自同构群作用在点集P、线集L和边集上是传递的。文献 [14] 确定了Wenger图的所有特征值及重数。关于Wenger图的更多结果参见文献 [15] [16] [17] [18] 。
在本文中,我们主要研究Wenger图如何做切换可以使得它的所有特征值都变为主特征值。我们的主要结论是Wenger图的任意特征值都包含一个无零元素的特征向量(见定理3.1),进一步,我们证明了符号Wenger图在任意地一个顶点处切换都会使得它所有特征值变为主特征值(见定理3.2)。
2. 预备知识
在这一节,我们介绍一些必要的定义和结论。
定义1 [19] 设是图G的特征值,如果对应的任意特征向量满足,我们称顶点对于是null;否则称对于是downer。
也就是说,设是图G一个特征值,代数重数为r,如果在中的代数重数是,则G的一个顶点对于是downer。因此,图G的特征值对应的特征空间包含一个无零元素的特征向量当且仅当图G的所有顶点关于是downer。
设是图G的自同构群,如果对于图G的任意顶点和存在一个自同构,使得,那么我们说图G是顶点传递图。类似地,如果对于图G的任意边和存在一个自同构,使得,那么我们说图G是边传递图。对于顶点传递图和边传递图,有以下定理。
定理2.1 [20] 顶点传递图的每个顶点对于每个特征值都是downer。
定理2.2 [20] 设是边传递图的一个特征值,那么存在一个无零元素的特征向量。
在主要结果的证明中,需要用到以下两个定理。
定理2.3 [20] 任意包含无零元素向量的特征子空间都有一个无零元素的正交基。
定理2.4 [21] 设q是一个素数幂,则
1) 当,和,q是偶数时,是q-正则半对称图。
2)是顶点传递图,q是偶数时,是顶点传递图。
3) 当时,是连通的;当时,有个连通分支,且每一个连通分支同构于。
3. 主要结果
在顶点处做切换,相当于改变特征值的特征向量中元素的符号。当特征值的所有特征向量中分量元素都为0时,在该点处做切换不影响特征值的主性。因此,我们重点讨论每个特征值都存在无零元素的特征向量的图。在本节中,我们首先证明以下定理。
定理3.1 设是Wenger图的任意特征值,则对应的特征空间都包含一个无零元素的特征向量。
证明:对于Wenger图的顶点集,定理2.4的证明有以下自同构映射:
当时;
.
因此,Wenger图是边传递图,且当时,是连通图,当时,有个连通分支,且每一个连通分支同构于。根据定理2.2,当时,存在一个无零元素的特征向量。下面我们证明时它对应的特征空间里存在一个无零元素的特征向量。
情况1:当时,是连通图。设Wenger图的两个部集分别为L和P,我们可以排列它的邻接矩阵的行和列,使具有以下形式:
.(2)
由此可得
. (3)
如果存在满足、满足分别使得、,那么就存在向量使得。由于齐次线性方程与齐次线性方程具有相同的解,因此。
1) 我们首先证明存在满足使得。设H是L上的点图(point-graph),H的顶点集是L,H中任意两个不同的线、相邻当且仅当存在使得在中与、相邻。更详细地说,如果存在使得,
(4)
那么、在H中是相邻的。又因为,其中。我们有和,进而H同构于凯莱图,其中
. (5)
由于凯莱图是顶点传递图 [22] ,因此H是顶点传递图。对于任意的,H的特征值可以表示成以下形式(详见 [14] ):
. (6)
其中。
由等式(6)得,当时,是H的特征值。设是H的邻接矩阵,通过对比实对称矩阵和实对称矩阵中的元素,有
.(7)
其中E表示n阶单位矩阵。利用定理2.1,H的特征值存在无零元素向量使得。在等式(7)两端同时乘以,得到。
2) 为了证明存在满足使得。类似地,我们在Wenger图的点集P上定义一个线图(line-graph),的顶点集是P,中任意两个不同的点,相邻当且仅当存在使得在中同时与,相邻。设是的邻接矩阵,则
. (8)
由于和有相同的谱,因此也是的一个特征值。下面我们证明是顶点传递图。根据,可知Wenger图在部集P上是传递的,因此温格尔图在部集P上是保路径长度的且它可以诱导出一个顶点传递图。也就是说,设,是的任意两个不相同的顶点,存在一个自同构映射
使得。具体映射过程如下所示:
自同构映射,出现在定理2.4的证明中。
情况2:当时,有个分支且每一个分支同构于。因此,的邻接矩阵有以下形式:
.(9)
显然,和具有相同的特征值。由情况1可得,的任意特征值总存在一个无零元素的向量。不妨设是的任意特征值,是在中的无零元素特征向量,则根据(9)得在中也有一个无零元素的特征向量,由个组成。证毕。
通过定理3.1,我们给出适当的切换使得符号Wenger图的所有特征值都变为主特征值。
定理3.2 设是一个符号图,其中底图G是Wenger图,符号函数,则在任意地一个顶点处切换都会使得它所有特征值变为主特征值。
证明:由定理3.1可知,符号图的每一个特征值都存在一个无零元素的特征向量。设是的一个特征值,代数重数为r,通过定理2.3,对应的特征空间存在一组无零元素正交向量基。进而符号图的特征空间存在一组无零元素正交向量基。由于G是q-正则图,所以q是的一个特征值且q存在一个全为1的特征向量。不妨设,则内积,其中。因此,存在一个切换使得,也就是说在的任意一点处做切换会使得它的所有特征值变为主特征值。证毕。
4. 总结
在本文中,我们通过寻找点图和线图的每个特征值都有一个无零元素的特征向量给出了Wenger图的任意特征值都包含一个无零元素的特征向量。基于这一事实,我们还给出了符号Wenger图在任意地一个顶点处做切换都会使得它所有特征值变为主特征值。然而,对于线性Wenger图的任意特征值是否存在一个无零元素的特征向量还是一个未知的问题。进一步的说,符号线性Wenger图在哪些顶点处做切换都会使得它所有特征值变为主特征值也是同一个未知的问题。通过本文的研究不仅为我们理解Wenger图提供了新的角度,并且为下一步研究符号线性Wenger图提供了思路。
基金项目
本文由贵州省科技厅项目(批准号:黔科合基础[2020]1Y405)资助。
NOTES
*通讯作者。
参考文献