图的规范化Laplace和规范化无符号Laplace特征多项式

陈丹丹, 马小玲

(新疆大学 数学与系统科学学院, 乌鲁木齐 830046)

1 引言与预备知识

2 规范化Laplace和规范化无符号Laplace特征多项式

定理1设G是有n个顶点的图, 则图G的规范化Laplace矩阵的特征多项式为

则

根据行列式的性质, 可得

(1)

将式(1)的每个行列式分解为两个行列式之和并继续该过程, 直到第n次可得

其中I表示对应顶点个数的单位矩阵,vi1,vi2,…,vik是从n个顶点中任意取出k个顶点, 且满足1≤i1

定理2设图G有n个顶点, 则图G的规范化无符号Laplace矩阵的特征多项式为

证明: 类似于定理1的证明, 有

根据行列式的性质, 可得

(2)

将式(2)的每个行列式分解为两个行列式之和并继续该过程, 直到第n次可得

其中I表示对应顶点个数的单位矩阵,vi1,vi2,…,vik是从n个顶点中任意取出k个顶点, 且满足1≤i1

3 矩阵的特征多项式

定理3设G是没有孤立点的图, 其顶点集为V={v1,v2,…,vn},S是图G的顶点子集, 则

证明: 设A(G)=(aij)(1≤i,j≤n)是图G的邻接矩阵, 则有

根据行列式的性质, 把上述行列式表示为两个行列式之和, 即

(3)

对式(3)中的每个行列式继续上述操作, 直到第n次可得

其中I表示对应顶点个数的单位矩阵,vi1,vi2,…,vik是从n个顶点中任意取出k个顶点, 且满足1≤i1

对于正则图, 根据定理3易得如下推论.

推论1若图G是n个顶点的r-正则图, 则

4 正则图的规范化Laplace和规范化无符号Laplace特征多项式

下面用图的邻接矩阵的特征多项式给出正则图的规范化Laplace和规范化无符号Laplace特征多项式的一般表达式.

定理4若图G是n个顶点的r-正则图, 则其规范化Laplace特征多项式为

证明: 设A(G)=(aij)(1≤i,j≤n)是图G的邻接矩阵.因为G是r-正则图, 并且R(G)=D-1/2(G)A(G)D-1/2(G), 则由L(G)=I-R(G), 可知

所以

(4)

根据行列式的性质, 将式(4)中的行列式表示为两个行列式之和为

(5)

将式(5)中的每个行列式分别表示为两个行列式之和并继续该过程, 直到第n次可得

其中I表示对应顶点个数的单位矩阵,vi1,vi2,…,vik是从n个顶点中任意取出k个顶点, 且满足1≤i1

根据图G的规范化无符号Laplace矩阵的定义并类似于定理4的证明思想, 可得如下定理, 即图G规范化无符号Laplace特征多项式的一般表达式.

定理5设图G是n个顶点的r-正则图, 则其规范化无符号Laplace特征多项式为

5 Middle图的邻接特征多项式

引理1[12]设G是有n个顶点、m条边的图,L(G)是图G的线图, 则其特征多项式为

(6)

定理6设图G有n个顶点和m条边, 则其Middle图M(G)的特征多项式为

证明: 若图G有n个顶点和m条边, 则由文献[1]中定理2.4.6可知,

(7)

由式(6)可得

(8)

将式(8)代入式(7)可得结果.证毕.