一类图的连通补图的特征值比较

鲁文鼎，叶永升，孙威

（1.淮北师范大学数学科学学院，安徽淮北235000；2.安庆师范大学数学与计算科学学院，安徽安庆246011）

一类图的连通补图的特征值比较

鲁文鼎1，叶永升1，孙威2①

（1.淮北师范大学数学科学学院，安徽淮北235000；2.安庆师范大学数学与计算科学学院，安徽安庆246011）

图的特征值在刻画连通图的性质时具有重要的作用.文章运用代数知识计算一类补图的邻接矩阵，进而计算该邻接矩阵的特征多项式.在已有定理基础上，分析连通补图的特征多项式的特征值，给出该连通补图的特征值比较.

邻接矩阵；特征值；补图；比较

0 引言

设A是n×n的矩阵，E是与A同阶的单位矩阵，则λE-A称为A的特征矩阵，||λE-A为A的特征多项式.设G是一个简单图，则图G的邻接矩阵记为，其中，当vi，vj相邻时，aij=1，否则图的特征值指的是该图邻接矩阵的特征值.特征方程的最小根称为最小特征值.在图类中，我们要借助图的邻接矩阵及其特征值来研究图的特性.

1 基础知识

定义1.1［1］如果，称图H为G的子图.

定义1.2［2］当且仅当两个顶点不在同一个Vi中，此二顶点相邻，则称图G为完全r部图，记成

引理1.1［3］设A是一实对称n×n矩阵，B为A的m×m阶主子阵，且λ1（A）≥λ2（A）≥…≥λn（A）以及λ1（B）≥λ2（B）≥…≥λm（B）分别为A和B的特征值.则对于i=1，2，…，m，有

在文献［4］中，设G=（V，E）为n阶简单图.对于向量X∈Rn，如果存在一个从V到X中对应值的映射φ，使得对于任意的u∈V有Xu=φ（u），则称X定义在G上.因此有

设λ是A（G）对应于特征向量X的特征值，当且仅当X≠0且对每个v∈V（G），有

目前，学者试图找到计算特殊图类特征值的方法，文献［5］给出无符号的拉普拉斯树的补图的特征值计算.此外，张恭庆［6］等对于求谱半径（最大特征值）的算法作了研究.

2 特征值的比较

定义2.1设KP和Kq为两个不交的完全图，u，v分别是KP与Kq中的点，，而点A和B是Kq的两个分别被点C和D固定的悬挂点，连接u，v所得的图记为G（p，q，1，2）.

定理2.1给定一个正整数n（n≥10），对于任意的正整数p和q满足p≥3，q≥1且p+q=n，p≥q≥1时，有

这个矩阵有n+2行n+2列.则有

令

此时，0不是最小特征值且-1也不是最小特征值.不妨设λ′1是最小特征值，故

即λ′1为fmin（）λ的最小根.为便于讨论，记

情形2：当q=2时，在原图的Kq部分，v点要么与C点重合，要么与D点重合，由对称性，不妨考虑v点与C点重合的情况.

显然，在补图中，D点除了与B点和C点不相邻外与其余的点都相邻，C点除了与D点、A点和u1点不相邻外与其余的点都相邻，A点除了与C点不相邻外与其余的点都相邻，B点除与D点不相邻外与其余点都相邻.此外，u2，u3，…，un-2只与C、D、A、B四点相邻，u1只与D、A、B三点相邻.故连通补图的邻接矩阵

这个矩阵有n+2行n+2列.则

设最小特征值为λ′2，此时

这里

对于λ≤-8时，显然有

情形3：当q≥3时，显然GC（）p，q，1，2为连通的非完全图，由引理1.1可知，故

作为下面讨论的引入，我们设X是GC（p，q，1，2）的第一特征向量，由文献［4］的特征等式（1.2）的结果，在Kp内的所有点除u1外，在X中对应着相同的值，即u2，u3，…，up所对应的特征向量的各个分量相同.

不妨设Kp内所有点除u1外在X中对应的特征分量为X1且在Kq内所有点除C、D、V外在X中都对应相同的值，记为X4.再设Xu1=X2，X3=XV，X5=XC，X6=XD.

事实上，XC与XD对应的特征分量是不同的，这是因为λXC=（p-1） X1+X2+XB，λXD=（p-1） X1+X2+XA，又XA不一定等于XB，故XC≠XD（λ≠0）.在补图中，A点与KP内所有的点均相邻，B点均与KP内所有的点相邻，又因为补图中A点与D点相邻，B点与C点相邻，则XC不一定等于XD，故将记XA=X7，XB=X8.

此外，在连通补图中，X1中存在u2点与Kq中点点相邻；u1与v点不相邻，故X2与Kp内除了V点外所有的点均相邻；X3在Kq内，Kq中对应的V点与C点、D点都不相邻，同时与Kq内所有的点都不相邻；除v点外，Kq内其他的点与Kp中的对应点均相邻；C点与Kp中所有的点都相邻且与B点相邻，但它与A点不相邻；D点与Kp中所有的点都相邻且与A点相邻，但它与B点不相邻；A点与C点不相邻；B点与D点不相邻，则有

将上述的等量关系表达式转换成矩阵等式

在畜牧业生产过程中，会产生大量的危害因素，不仅为生态环境带来负担，还影响了我国畜牧业的生产与发展。基于此，只有全面掌握常见的生产污染摸，积极制定解决措施，以此降低畜牧业生产污染，保护我国生态环境，推动畜牧业可持续发展。对此，下文对畜牧业常见的生产污染展开探讨。

记

则

子情况（1）：

令

令

子情况（2）：当q≥p+11时，由上述证明有

故对q≥3时的情形，有

由于q=1时的最小特征值比q=2时的最小特征值要大，记q=1时的最小特征值是λ′1，则它是的根；记q=2时的最小特征值是λ′2，则它是的根.因为

故比较q=3和q=2时的特征值.

设q=3与q=2时，对应的特征多项式分别为F1（）x和F2（）x，则

记

故

［1］TUTTE W T.Graph Theory［M］.北京：机械工业出版社，2004.

［2］王树和.图论［M］.北京：科学出版社，2011.

［3］HAEMERS W.Interlacing eigenvalue and graphs［J］.Linear Algebra Appl，1995，227：593-616.

［4］FIEDLERM.A property of eigenvectors of nonegative symmetric matrices and its application to graph theory［J］.Czech Math J，1975，25：619-633.

［5］LI S C，WANG S J.The least eigenvalue of the signless Laplacian of the complements of tree［J］.Linear Algebra Appl，2012，436：2398-2405.

［6］CHANG K C，PEARSON K，ZHANG T.Primitivity，the convergence of the NZQ method，and the largest eigenvalue for non⁃egative tensors［J］.SIAM J Matrix Anal Appl，2011，32：806-819.

The Comparison of Eigenvalue of the Graph with Two Leaves and Complement Connected

LU Wending1，YE Yongsheng1，SUN Wei2
（1.School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China；2.School of Mathematics and Computation Sciences，Anqing Normal University，246011，Anqing，Anhui，China）

The characteristic value of the graph has the important function in recording the properties of the connected graphs.This essay calculated the adjacency matrix of some graphs by using algebraic knowledge. What is more，it also calculated the characteristic polynomial of the adjacency matrix.Based on the fundamen⁃tal of the theorem recently，the essay analyzed the characteristic value of characteristic polynomial on the con⁃nected and complementary graphs，and compared the characteristic value of the connected and complementa⁃ry graphs.

adjacency matrix；eigenvalue；complementary graph；comparison

O 157.5

A

2095-0691（2016）03-0016-05

2016-04-18

安徽省自然科学基金项目（1408085MA08）；安徽省高校自然科学基金项目（KJ2016A633）

鲁文鼎（1991-），男，安徽当涂人，硕士生，研究方向为图论及其应用；通讯作者：叶永升（1964-），男，安徽嘉山人，教授，主要从事图论及其应用研究.