两类双圈图最大特征值的比较

Comparison of the Maximum Eigenvalues of Two Types of Bicyclic Graphs

摘要: 本文研究了两类连通双圈图的最大特征值，得出了随着n的增大，双圈图S_n(3,3)和θ_n(3,3)的最大特征值也随之增大；同时给出了n≥5在的条件下，S_n(3,3)和θ_n(3,3)的最大特征值的比较。

Abstract: This paper studies the maximum eigenvalues of two types of connected bicyclic graphs, and finds that as n increases, the maximum eigenvalues of bicyclic graphs S_n(3,3) and θ_n(3,3) also increase; at the same time, it also gives a comparison of the maximum eigenvalues of S_n(3,3) and θ_n(3,3) under the condition of n≥5.

1. 引言

1.1. 背景介绍

设 $G=\left(V,E\right)$ 是一个简单的无向连通图，其中顶点集 $V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ ，边集 $E\left(G\right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ 如果 $m=n+1$ ，那么G被称为双圈图，图G的顶点数n被称为G的阶。G的邻接矩阵记为 $A\left(G\right)={\left(a_{ij}\right)}_{n\times n}$ ，如果 $v_i$ 与 $v_j$ 相邻，那么，否则。的特征多项式记为，的最大特征值也被称为G的谱半径，用表示。由于是非负不可约对称矩阵，所以它的最大特征值为单根，且所有的特征值均为实数，记其特征值为，由矩阵理论知有正特征向量与对应，我们称与对应的正单位特征向量为G的Perron向量。

在图论中，G的一条路是指一个有限非空序列，它的项交替地为顶点和边，且互不相同，使得对，的端点是和，那么称W是从到的一条长为k的路。特殊地，在G中，若和重合，则W是一个长为k的圈，记为。在具有n个顶点的图G中，其中一个点的度为，分别与其他个点相连，其他个点只与度为的点相连，这样的图称为星图。

我们将圈的某一点与圈的某一点粘合，仅在粘合点处连接星图得到的n阶连通双圈图记作(粘合点为星图的非一度点) (见图1)。将圈上的任意两点相连，形成圈和圈，在其中任意一个连接处连接星图得到的n阶连通双圈图记作(见图1)。

Figure 1.Bicyclic Graphs and

图1.双圈图和

关于双圈图的研究已经有很长时间了，双圈图的性质也逐步被人们发现。1986年，Brualdi和Solheid [1] 提出，给定一个图的集合，在这个集合中找出谱半径的上界，并刻画达到这个上界的极图。2004年，Yu和Tian [2] 找出了在具有匹配数m的n个顶点的所有双圈图中谱半径最大的一类图。2010年，Liu Yingluan和Liu Bolian [3] 找出了双圈图度序列π相同的情况下谱半径最大的一类图。但是没有对几类比较有特点的双圈图的最大特征值展开详细研究。

1.2. 本文贡献

基于以上研究，本文主要通过对两类连通双圈图和的最大特征值进行研究，利用二次型以及双圈图的邻接矩阵的特征多项式进行分析，确定它们的最大特征值的大小。

2. 预备知识

如果，，并且是在上的限制，则称图H是G的子图。如果，但时，则记为，并且H称为G的真子图。

定理2.1 [4]：设G是具有n个顶点的连通图，如果是G的一个子图，那么。

定理2.2 [4]：对于任意正整数p和q，的特征值为，和0，并且特征值0的重数为。特殊地，的特征值为，和0，并且特征值0的重数为。

定理2.3 [4]：设G是一个有个顶点的连通图，并令A是G的邻接矩阵，那么下面命题成立：

1) A有一个特征值，存在一个对应的特征向量。

2) 对于A的任意一个特征值，有。此外，当且仅当G是二部图时，才是A的一个特征值。

3) 如果是A的对应于特征值的一个特征向量，那么存在一个，使得。

在定理2.4的1)中提到的G的这种特征值，被称为G的Perron特征值，而其对应的特征向量x被称为Perron特征向量。注意到2)中G的Perron特征值和最大特征值(即)相同。如3)中所示，Perron特征向量是唯一的，最多相差一个标量倍。

定理2.4 [4]：设A是一个对称矩阵，且其特征值以非增顺序排列。令表示常用的欧几里得范数，即。那么。

定理2.5 [5]：令G是具有 ()个顶点的图，顶点集。如果是通过在G中的上添加k个悬挂点得到，那么

其中对应于顶点，且。

3. 主要结论

定理3.1：当双圈图的点数n变大时，其最大特征值也变大，即(见图2)。

Figure 2.Bicyclic Graphs and

图2.双圈图和

证明：设是的单位Perron向量，是对应于的顶点的分量值。记是的邻接矩阵，是的邻接矩阵，即，其中，。现在的图上增加一个孤立点，所得到的图记作，其对应的邻接矩阵为。的最大特征值对应的特征向量为。

又因为，，所以。

若，则成立，即

成立。

然而

矛盾。

因此，。

定理3.2：当双圈图的点数n变大时，其最大特征值也变大，即(见图3)。

Figure 3.Bicyclic Graphs and

图3.双圈图和

证明：同定理3.1的证明，很容易证得。

定理3.3：当时， (见图4)。

证明：删除个的悬挂点得到的图记为G，删除个的悬挂点得到的图记为。

由定理2.5可得：

Figure 4. Bicyclic Graphs and

图4. 双圈图和

其中；；

那么，分别是和的最大根。又因为和都以作为真子图，所以根据定理2.1和定理2.2可得：

令，则，。

所以，当且时，有，进一步有，，那么，而，则。

又因为，并且当时，，所以根据的性质，当时，有。

例3.1：通过Matlab很容易计算出，，，，，，从而，，，，。因此，在一定程度上验证了定理3.1~定理3.3的正确性。

4. 结论与展望

本文主要研究了两类连通双圈图和的最大特征值，利用二次型以及双圈图的邻接矩阵的特征多项式进行分析确定它们最大特征值的大小，从而得出一些有意义的结论，使我们对这两类双圈图的最大特征值有了更加深入的理解。

我们也将会进一步研究双圈图和随n的变化其最小特征值的变化情况，以及在n一定的条件下，双圈图和的最小特征值的比较。