陈丹丹, 马小玲
(新疆大学 数学与系统科学学院, 乌鲁木齐 830046)
定理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设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-正则图, 则 下面用图的邻接矩阵的特征多项式给出正则图的规范化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特征多项式为 引理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)可得结果.证毕.
