王展青，王力工*，梅若星，翟若男，董占鹏

（西北工业大学　理学院应用数学系，陕西西安710072）



两类双圈图的Laplacian谱确定问题

王展青，王力工*，梅若星，翟若男，董占鹏

（西北工业大学理学院应用数学系，陕西西安710072）

设G =（V（G），E（G））是一个简单连通图，V（G），E（G）分别表示图G的顶点集和边集.如果与图G同Laplacian谱的图都与G同构，则称图G由它的Laplacian谱确定.该文定义了两类双圈图Q（n；n1，n2，···，nt）和B（n；n1，n2），证明了双圈图Q（n；n1），Q（n；n1，n2），Q（n；n1，n2，n3）和双圈图B（n；n1，n2）分别由它们的Laplacian谱确定.

Laplacian矩阵；Laplacian特征多项式；Laplacian谱

§1　引　言

本文所考虑的图都是简单连通无向图.双圈图是指一个边数比顶点数多1的简单连通图.根据一个n阶双圈图的双圈相对位置的不同，可以将n阶双圈图划分为三类，分别为An（p，q），Bn，m（p，q）和Cn（p，q），其中:An（p，q）表示其中两个圈Cp和Cq有且只有一个公共顶点的n阶双圈图，Bn，m（p，q）表示其中两个圈Cp和Cq有m（≥2）个公共顶点的n阶双圈图，Cn（p，q）表示其中两个圈Cp和Cq没有公共顶点的n阶双圈图.设图G =（V（G），E（G））的顶点集和边集分别为V（G）= ｛v1，v2，···，vn｝和E（G）.用A（G）表示图G的邻接矩阵，di= di（G）= dG（vi）表示顶点vi的度，D（G）= diag（d1，d2，···，dn）表示顶点度对角矩阵. deg（G）=（d1，d2，···，dn）表示图G的顶点度序列，当顶点度序列中有k个相等的di时，可将这k个di记为dki.矩阵L（G）= D（G）- A（G）为图G的Laplacian矩阵.多项式ϕ（L（G）；µ）= det（µIn- L（G））= l0µn+ l1µn-1+···+ ln表示图G的Laplacian特征多项式，In是一个n×n阶单位矩阵.下文将ϕ（L（G）；µ）写成ϕ（G；µ）或直接写成ϕ（G）.设µ1≥µ2≥···≥µn是L（G）的特征值，它们构成了图G的Laplacian谱.如果两个图有相同的Laplacian谱，就说它们是Laplacian同谱图.如果与图G同Laplacian谱的图都与图G同构，则称图G可由它的Laplacian谱确定.

“哪些图可由它们的谱确定？”这一典型问题是由G¨unthard和Primas于1956年提出的［1］，它起源于化学，是图谱理论中一个有趣且困难的问题. 1966年，Fisher在考虑……