图的Sum-connectivity指标与其无符号拉普拉斯谱半径

王月卿, 林雅津

(1.闽南师范大学 计算机学院, 福建 漳州 363000; 2.闽南师范大学 数学与统计学院, 福建 漳州 363000)

等式成立当且仅当G≅Sn.

本文讨论的图均为无向连通图,设G=(V,E),其中V(G)为图G的顶点集,其阶数为n;E(G)为图G的边集,其阶数为m;用dv表示与顶点v∈V(G)相关联的的边数,称为顶点v的度;顶点数为n的完全图,星图和路分别用Kn,Sn及Pn表示.

用q(G)表示无符号拉普拉斯矩阵Q(G)=D(G)+A(G)的谱半径,即矩阵Q(G)的最大特征值,其中D(G)和A(G)分别为图G的度对角矩阵和邻接矩阵;用λ(G)表示图G的谱半径,即矩阵A(G)的最大特征值.

Zhou等[1]定义并研究了图G的Sum-connectivity指标,其定义如下:

更多关于图的Sum-connectivity指标的性质,可参考文献1～3.

对于简单图G,其性质可以借助各种形式的图的拓扑指标来衡量,对其各自拓扑指标的研究,目前已有大量的成果.近期,关于图的特征值(特别是q(G)和λ(G))与图的拓扑指标之间关系的研究受到了广泛关注.

本文主要研究的是χ(G)与q(G)之间的关系,证明了以下结论.

定理1设G为具有n≥3个顶点的连通图,则

等号成立当且仅当G≅Sn.

1 预备知识

首先,我们将给出一些在证明过程中将会用到的已有结论.在文献4～5中分别给出了无符号拉普拉斯谱半径和邻接矩阵谱半径的上界.

引理1.1[6]设G为具有n个顶点,m条边的连通图,则

等号成立当且仅当G≅Kn或G≅Sn.

引理1.2[7]设G为具有n个顶点,m条边的连通图,λ(G)为邻接矩阵的谱半径,则

等号成立当且仅当G≅Kn或G≅Sn.

引理1.3[8]设G为具有n个顶点的任意连通图,λ(G)为邻接矩阵的谱半径,则

引理1.4[1]令G为具有m条边的连通图,则

引理1.5设G为具有n个顶点,m条边的连通图,则

证明由引理1.3和1.4,则

结论成立.

2 定理1的证明

在给出定理1的证明之前,首先证明以下事实,设G为具有n≥5个顶点,m条边的连通图,则有

引理2.1设G为具有n≥5个顶点,m条边的简单连通图,则

证明因为G为简单连通图,所以有m≥n-1.以下将根据m的大小分两种情况对引理2.1进行证明.

(1)当m=n-1时

令

则

(1)

其中

g(m)=(m-n+1)[nm2+(n-4)(n-1)m-(n3-4n2+4n-2)].

(2)当时m≥n时

注意到

g(m)=(m-n+1)[nm2+(n-4)(n-1)m-(n3-4n2+4n-2)],

显然

有g(m)≥0.

因为

所以有

综上所述,当m≥n-1时,有

引理2.2设G为具有n≥5个顶点,m条边的简单连通图.若

下面分两种情况进行讨论:

(2)当G≅Sn时,m=n-1,则有

由引理2.1和2.2,可得以下结论.

引理2.3设G为具有n≥5个顶点的简单连通图.则

等号成立当且仅当G≅Sn.

引理2.4设G为具有n=3个顶点的简单连通图.则

等号成立当且仅当G≅S3.

表1 顶点数n=3

引理2.5设G为具有n=4个顶点的简单连通图.则

等式成立当且仅当G≅S4.

表2 顶点数n=4

定理1的证明由引理2.3, 2.4, 2.5易得.