卢鹏丽, 刘晓刚

(1.兰州理工大学 计算机与通信学院，甘肃 兰州 730050; 2.墨尔本大学 数学与统计学院，澳大利亚 墨尔本 3010)



似双星树H(p,n,q)由Laplacian谱刻画

卢鹏丽1, 刘晓刚2

(1.兰州理工大学 计算机与通信学院，甘肃 兰州 730050; 2.墨尔本大学 数学与统计学院，澳大利亚 墨尔本 3010)

摘要：似双星树是恰好有两个结点的度大于2的树。用H(p,n,q)表示将路图Pn的两个悬挂点分别与星图S(1,p)及S(1,q)的中心点重合所得到的一类似双星树。首先得到了顶点的度序列，然后由谱性质证明了似双星树H(p,n,q)由Laplacian谱确定，扩大了谱确定图的范围。

关键词：邻接谱；Laplacian谱；A-同谱图；L-同谱图；线图

1基本引理

引理1[13-23]对任意图，由它的邻接谱或Laplacian谱可确定：

1) 结点的个数；

2) 边的条数。

对任意图，由它的邻接谱可确定：

3) 图中任意长度的闭回路的数目。

对任意图，由它的Laplacian谱可确定：

4)图的组成分支数目；

5)生成树的个数；

6)结点度的平方和。

引理2[24]对任意图，长度为4的闭回路的数目等于2倍的边数加上4倍的长度为2的导出路的数目，再加上8倍的长度为4的圈图的数目。

原图G的线图记为(G)。在线图(G)中，其结点相当于原图G的边，当且仅当原图G中的两条边有公共结点时，线图(G)中的结点则为邻接点。

引理3[25]设T是有n个结点的树，(T)是它的线图，则有

式中：i=1,2,…,n-1。

引理4[26]设u是图G的一个结点，从图G中去掉结点u及其结点u的关联边得到子图G-u，有

引理5[2]设e是图G的一条边，从图G中去掉边e得到子图G′=G-e，有

式中：i=1,2,…,m。

引理7[27-28]设图G的结点集V(G)和边集E(G)都不为空，有

式中：mi是图G中所有与结点vi相邻的结点的度的平均值。

引理 8[29]设图G是结点数大于等于3的连通图，则有