资源描述：
《几类图的无符号laplace矩阵的行列式》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、几类图的无符号Laplace矩阵的行列式邱玮（福州外语外贸学院，福建福州350202）摘要：我们知道n个顶点的图G的无符号Laplace特征多项式为，Cvetkovic等[6]给出了其系数bi的组合解释.我们发现det(Q(G))的值恰好是常数项系数bn.于是可以根据bn的组合解释来讨论图G的无符号Laplace矩阵的行列式.本文主要研究n个顶点的树、连通单圈图与连通双圈图的无符号Laplace矩阵的行列式的计算问题，给出了计算这些图类的无符号Laplace矩阵的行列式的一般方法，对研究图的无符号Laplace矩阵的行列式有着重要的意义..jyqk(G)=
2、E
3、表示G的边数,简记为m.对u,
4、v∈V(G)，若e=uv∈E(G)，则称u和v相邻，同时也称u及v与e相关联.若e1,e2∈E(G)有一个公共顶点，则称e1和e2相邻.定义1.2图G=(V,E)中，与顶点v相关联的边数，称为顶点v的度，记为dG(v)，简记为d(v).定义1.3图G=(V,E)中，如果两条边有相同的两端点，则称它们为重边或平行边，如果一条边的两端点相同，就称它为环.称不包含环和重边的图为简单图.本文主要讨论简单图.定义1.4对于图G和H，如果V(H)?哿V(G)，E(H)?哿E(G)，则称H是G的子图,如果H是G的子图,并且V(H)=V(G),则称H是G的生成子图.定义1.5如果图G的一个顶点和边的交替序列
5、v0e1v1e2v2…vm-1emvm使得对1≤i≤m，边ei的两个端点是vi-1和vi，则称该序列为G的一条路径.又如果边e1,e2,…,em互不相同，则称该路径为G的一条迹（或叫链）.顶点互不相同的迹称为G的一条路.路中边的条数称为该路的长度,图G中u,v两点的距离是指以u与v为起止点的u-v路的最短路长，记为dG(u,v).定义1.6对于图G的两个顶点u和v，如果G中存在一条路，记为(u,v)路，则称u和v是连通的.如果一个图的每一对顶点都至少有一条路连结，则称该图为连通图.定义1.7在图G中顶点的连通关系下，可将V(G)划分成有限个等价类，每个等价类构成G的子图，称为G的一个连通分支
6、.定义1.8圈C是指顶点集为V(C)={v1,v2,…,vn}，边集为E(C)={v1v2,…,vn-1vn,vnv1}的图，记为圈Cn，n=
7、E(C)
8、为圈的长度.按n是奇数还是偶数，称Cn是奇圈或偶圈.定义1.9没有圈的连通图称为树，记为T，每个连通分支皆为树的图称为森林.如果T为树，则n(T)=m(T)+1，这里n(T)与m(T)分别为T的顶点数与边数.定义1.10由树添加一条边所得到的连通图称为单圈图,记为U.显然，n(U)=m(U).定义1.11由树添加两条边所得到的连通图称为双圈图,记为((G)=n(G)，所以当g为奇数时，bn=4；当g为偶数时，bn=0.综上所述：下面我们再考
9、虑双圈图的无符号Laplace矩阵的行列式的计算问题，我们得到如下三个定理.定理3.3设G是n个顶点的连通双圈图，其中两个圈为C1与C2，它们的长度分别为g1与g2，且C1与C2相交于一个顶点，G的无符号Laplace矩阵为Q(G)=D(G)+A(G)，则：定理3.4设G是n个顶点的连通双圈图，其中两个圈为C1与C2，它们的长度分别为g1与g2，且C1与C2不相交，C1与C2之间距离为g3，G的无符号Laplace矩阵为Q(G)=D(G)+A(G)则：定理3.5设G是n个顶点的连通双圈图，其中两个圈为C1与C2，它们的长度分别为g1与g2，若C1与C2有公共边，且公共边的数目为g4，G的无符
10、号Laplace矩阵为Q(G)=D(G)+A(G)则：3.1C1与C2相交于一个顶点，如图1.（1）当g1,g2都为偶数时，去掉任何一条边都不能形成n条边的TU-子图.根据定理2.2，det(Q(G))=bn=0.（2）当g1为奇数，g2为偶数时，去掉C2以外的任何一条边都不能形成n条边的TU-子图；去掉C2上的任何一条边都形成G的一个n条边的TU-子图H，此时?椎(H)=4.根据定理2.2，det(Q(G))=bn=（3）当g1为偶数，g2为奇数时，同（2）的情况一样可得：det(Q(G))=4g1.（4）当g1,g2都为奇数时，去掉C1,C2以外的任何一条边都不能形成n条边的TU-子图；
11、去掉C1,C2上的任何一条边都会形成G的一个n条边的TU-子图H，此时?椎(H)=4.又因为C1,C2的长度分别为g1,g2，根据定理2.2，3.2C1,C2不相交，且C1,C2之间的距离为g3，如图2所示.（1）当g1,g2都为偶数时，去掉任何一条边都不能形成n条边的TU-子图.根据定理2.2，det(Q(G))=bn=0.（2）当g1为奇数，g2为偶数时，去掉C2以外的任何一条边都不能形成n条边的TU-子
