论文部分内容阅读
设 G=(V,E)是简单连通图，它的顶点集 V(G)={v1,v2,…,vn}和边集E(G)={e1，e2,…，em}，分别用A(G)=(aij)和D(G)=diag(d1,d2,…,dn)表示图G的邻接矩阵和度对角矩阵，其中di表示顶点vi的度，当vi和vj相邻时aij=1，当vi和vj不相邻时aij=0.图G的拉普拉斯矩阵L(G)=D(G)-A(G)，容易知道L(G)是一个半正定的实对称奇异矩阵，把L(G)的特征值从大到小排列如下： λ1(G)≥λ2(G)≥…≥λn-1(G)≥λn(G)=0. 因为λn-1(G)>0当且仅当图G是连通图，所以λn-1(G)称为图G的代数连通度. 若m=n+1则称图G为双圈图.若图中所含的两个圈有且仅有一个公共顶点，则称该图为相切双圈图；若图中所含的两个圈没有公共顶点，则称该图为相离双圈图；若图中所含的两个圈至少有两个公共顶点，则称该图为相交双圈图.本文主要对相切双圈图中前六大代数连通度的图类，相离双圈图中前十四大代数连通度的图类和相交双圈图中第五到第十大代数连通度的图类分别进行排序.