本文只研究简单图。设G=(V(G),E(G))表示一个顶点集为V(G)={v₁,v₂,…,v_n}、边集为E(G)的图，其中顶点v₁,v₂,…,v_n按度的大小降序排列。结点v_i的度记为d_i=d_i(G)=d_G(v_i)，按结点度降序排列的度序列记为deg(G)=(d₁,d₂,…,d_n)。图G的邻接矩阵A(G)是一个n×n的矩阵，当结点v_i和结点v_j邻接时矩阵元素(i,j)为1，否则为0。L(G)=L(G)-A(G)表示图G的Laplacian矩阵，其中L(G)是n×n的对角矩阵，其对角元素为d₁,d₂,…,d_n。矩阵A(G)和L(G)的特征根分别称为图G的邻接特征根和Laplacian特征根，用λ₁(G)≥λ₂(G)≥…≥λ_n(G)和μ₁(G)≥μ₂(G)≥…≥μ_n(G)表示。矩阵A(G)和L(G)的特征根(包括重数)分别称为图G的邻接谱和Laplacian谱。如果两个图的Laplacian谱相同，那么这两个图是L-同谱图。如果不存在与之L-同谱且不同构的图，那么称图G是由Laplacian谱确定的。更多谱确定的背景知识参阅文献[1, 2, 3]。迄今，有些图类^{[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]}已经被证明由它们的邻接谱确定或Laplacian谱确定。然而，只有少数特殊结构的树图被证明是由Laplacian谱确定的，总结如下：任意路图都由Laplacian谱确定^[3]。树图Z_n,T_n和W_n由Laplacian谱确定^[5]。所有的T型树都由Laplacian谱确定^[6]。所有的似星树都由Laplacian谱确定^[7]。所有的centipede图都由Laplacian谱确定^[8]。满足b∉{1,3}的所有树图M_a,b,c(a,b,c≥1)是由Laplacian谱确定^[9]。所有的树图H_n(p,p)(n≥2,p≥1)都由Laplacian谱确定^[10]。所有树图T_n²都由Laplacian谱确定^[11]。满足n²≤k的所有香蕉树B_n,k都由Laplacian谱确定^[12]。

1 基本引理

引理1^{[3, 23]} 对任意图，由它的邻接谱或Laplacian谱可确定：

1) 结点的个数；

2) 边的条数；

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

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

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

4)图的组成分支数目；

5)生成树的个数；

6)结点度的平方和。

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

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

引理3^[25] 设T是有n个结点的树，$\ell \left( T \right)$是它的线图，则有

$ {{\mu }_{i}}\left( T \right)={{\lambda }_{i}}\left( \ell \left( T \right) \right)+2 $

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

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

$ {{\mu }_{i}}\left( G \right)\ge {{\mu }_{i}}\left( G-u \right)\ge {{\mu }_{i+1}}\left( G \right)-1 $

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

$ \begin{matrix} {{\mu }_{i}}\left( G \right)\ge {{\mu }_{i}}\left( G' \right)\ge {{\mu }_{2}}\left( G \right)\ge {{\mu }_{2}}\left( G' \right)\ge \\ \ldots {{\mu }_{n-1}}\left( G \right)\ge {{\mu }_{n-1}}\left( G' \right)\ge {{\mu }_{n}}\left( G \right)={{\mu }_{n}}\left( G' \right)=0 \\ \end{matrix} $

引理6^[3] 假设N是n×n的对称矩阵，有特征根α₁≥α₂≥…≥α_n，假设矩阵N的m维的主子阵的特征根为α'₁≥α'₂≥…≥α'_m，则有

$ {{\alpha }_{i}}\ge \alpha {{'}_{i}}\ge {{\alpha }_{n-m+i}} $

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

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

$ \begin{matrix} {{d}_{1}}+1\le {{\mu }_{1}}\left( G \right)\le \\ \max \left\{ \frac{{{d}_{i}}\left( {{d}_{i}}+{{m}_{i}} \right)+{{d}_{j}}\left( {{d}_{j}}+{{m}_{j}} \right)}{{{d}_{i}}+{{d}_{j}}},{{v}_{i}}{{v}_{j}}\in E\left( G \right) \right\} \\ \end{matrix} $

式中，m_i是图G中所有与结点v_i相邻的结点的度的平均值。

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

$ {{\mu }_{2}}\left( G \right)\ge {{d}_{2}} $

引理 9^[30]设图G是结点数大于等于4的连通图，则有

$ {{\mu }_{3}}\left( G \right)\ge {{d}_{3}}-1 $

2 主要结论

似双星树是恰好有两个结点的度大于2的树。将路图P_n的两个悬挂点分别与星图S_1,p及S_1,q的中心点重合得到的一类似双星树表示为H(p,n,q)，如图 1所示，其中p≥q≥1。

命题1 1) 若n=1，则H(p,n,q)≅K_1,p+q且是由Laplacian谱确定的^[7]。

2)若n=2或n=3，则H(p,n,q)是由Laplacian谱确定的^[31]。

3)若p=q=1，则H(1,n,1)≅P_n+2且是由Laplacian谱确定的^[3]。

4)若p>q=1，则H(p,n,1)是似星树且是由Laplacian谱确定的^[7]。

5)若p=q≥2，则H(p,n,q)≅H_n(p,p)且是由Laplacian谱确定的^[10]。

由命题1知，只需考虑似双星树H(p,n,q)满足n≥4且p>q≥2是否由Laplacian谱确定即可。下面，首先给出似双星图的最大特征根，次大特征根及第三大特征根的界值。

引理10 设G=H(p,n,q)满足n≥4且p>q≥2，则

1)p+2≤μ₁(G)≤p+2+$ \frac{1}{p+2} $

2)q+2≤μ₂(G)≤q+3+$ \frac{1}{q+2} $

3)μ₃(G)<4

证明：1)由引理7，通过简单的计算即可得到最大特征根的界值。

2)设u和v是图G中度分别为p+1和q+1的结点，由引理4知 μ₁(G)≥μ₁(G-u)≥μ₂(G)-1.又由引理7知μ₁(G-u)≤q+2+$\frac{1}{q+2}\ $.得

$ {{\mu }_{2}}\left( G \right)\le {{\mu }_{1}}\left( G-u \right)+1\le q+3+\frac{1}{q+2} $

去掉图G的一条边(这条边的端点既不包含结点u也不包含结点v)得到子图G₁。很明显图G₁由两个连通的部分组成。由引理7知，每一部分的最大特征根至少为q+2，即μ₂(G₁)≥q+2.再由引理5得μ₂(G)≥μ₂(G₁)≥q+2.

3)删掉Laplacian矩阵L(G)中对应结点u和v的行和列得到(p+n+q-2)×(p+n+q-2)维的主子阵M_uv。显然，M_uv的最大特征根小于4。由引理6得μ₃(G)<4。

引理11 图G=H(p,n,q)满足n≥4且p>q≥2，假设图G'是图G的L-同谱图。那么G'也是似双星树，并且度序列为

$ \deg \left( G' \right)=\left( p+1,q+1,\overbrace{2,\ldots ,2}^{n-2},\overbrace{1,\ldots ,1}^{p+q} \right) $

证明：由引理1的1) 2) 3)和4)知，G'为有n+p+q个结点，n+p+q-1条边的树。设(d₁,d₂,…,d_n+p+q)是图G'的非递增度序列，n_i表示图G'中度为i的结点的个数，其中i=1,2,…,d₁。

由引理7和引理10的1)可得d₁+1≤μ₁(G')≤p+2+$ \frac{1}{p+2} $，进而得d₁≤p+1。

由引理8和引理10的2)可得d₂≤μ₂(G')=μ₂(G)≤q+3+$\frac{1}{q+2}\ $，进而得d₂≤q+3。

由引理9和引理10的3)可得d₃≤μ₃(G')+1=μ₃(G)+1<5，进而得d₃≤4。

另一方面，由引理1的1)2)6)可以得到如下的等式，

$ \sum\limits_{i=1}^{{{d}_{1}}}{{{n}_{i}}=n+p+q} $

(1)

$ \sum\limits_{i=1}^{{{d}_{1}}}{i{{n}_{i}}=2\left( n+p+q-1 \right)} $

(2)

$ \sum\limits_{i=1}^{{{d}_{1}}}{{{i}^{2}}{{n}_{i}}=2{{\left( p+1 \right)}^{2}}}+{{\left( q+1 \right)}^{2}}+4{{\left( n-2 \right)}^{2}}+p+q $

(3)

综合上述三个等式可以得到

$ \sum\limits_{i=1}^{{{d}_{1}}}{\left( {{i}^{2}}-3i+2 \right){{n}_{i}}={{p}^{2}}}+{{q}^{2}}-p-q $

(4)

由引理3可知线图$ \ell \left( G' \right) $和线图$\ell \left( G \right)$是A-同谱图。又由引理1的3)可知线图$ \ell \left( G' \right) $和线图$\ell \left( G \right)$有相同数目的三角形，即

$ \sum\limits_{i=1}^{{{d}_{1}}}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}=\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)}+\left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right) $

(5)

上面已经证得d₁≤p+1，d₂≤q+3和d₃≤4。下面分两种情况确定图G'的度序列。

情形 1 q=2或q=3。假设d₁<p+1。那么度为p+1的结点数目n_p+1=0，由公式(4)、(5)得

$ \begin{matrix} \left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)=\sum\limits_{i=1}^{{{d}_{1}}}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}\le } \\ \frac{P}{6}\sum\limits_{i=1}^{{{d}_{1}}}{\left( i-1 \right)\left( i-2 \right){{n}_{i}}=\frac{P}{6}\left( {{p}^{2}}+{{q}^{2}}-p-q \right)} \\ \end{matrix} $

(6)

如果q=2，那么就有p≥3。把q=2代入公式(6)可以得到p²-3p+6≤0，这与p≥3矛盾。

如果q=3，那么就有p≥4。把q=3代入公式(6)可以得到p²-7p+24≤0，这与p≥4矛盾。

经上述讨论知，图G'的结点的最大度d₁=p+1，即度为p+1的结点数目n_p+1≥1。

现在假设n_p+1≥2，也就是说G'至少存在两个结点的度为p+1。有公式(5)可得

$ \begin{matrix} \left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)=\sum\limits_{i=1}^{{{d}_{1}}}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}\ge } \\ 2\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)+\sum\limits_{i=1}^{P}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}} \\ \end{matrix} $

就有$ \left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)-\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)\ge \sum\limits_{i=1}^{P}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}\ge }0 $。这与q<p矛盾，因此度为p+1的结点数目n_p+1=1。下面进一步确定其它结点的度。

如果q=2，由公式(5)可得n₃=1和n_i=0，其中i=4,5,…,p。由公式(1)、(2)可得n₂=n-2和n₁=p+2。由此图G'的度序列为

$ \deg \left( G' \right)=\left( p+1,3,\overbrace{2,\ldots ,2}^{n-2},\overbrace{1,\ldots ,1}^{p+2} \right) $

如果q=3，由公式(5)可得n₄≤1和n_i=0，其中i=5,…,p。由公式(1)、(2)和(3)可得n₄=1，n₃=0，n₂=n-2和n₁=p+3。由此图G'的度序列为$ \deg \left( G' \right)=\left( p+1,4,\overbrace{2,\ldots ,2}^{n-2},\overbrace{1,\ldots ,1}^{p+3} \right) $。

情形2 q≥4。明显可得到d₁≥4。因为若d₁=3，由公式(4)和(5)得${{n}_{3}}=\frac{1}{2}\left( {{p}^{2}}+{{q}^{2}}-p-q \right) $和${{n}_{3}}=\left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right) $ ，矛盾。另一方面，联合公式(4)和(5)得

$ \begin{matrix} \sum\limits_{i=1}^{{{d}_{1}}}{\left( i-1 \right)\left( i-2 \right)\left( i-3 \right){{n}_{i}}=} \\ {{p}^{3}}+{{q}^{3}}-3{{p}^{2}}-3{{q}^{2}}+2p+2q \\ \end{matrix} $

进而可得

$ \begin{matrix} 6{{n}_{4}}+\sum\limits_{i=1}^{{{d}_{1}}}{\left( i-1 \right)\left( i-2 \right)\left( i-3 \right){{n}_{i}}=} \\ p\left( p-1 \right)\left( p-2 \right)+q\left( q-1 \right)\left( q-2 \right) \\ \end{matrix} $

(7)

已证得d₃≤4，也就是说，图G'中至多存在两个度大于4的结点，下面从三个方面考虑这个问题。

情形2.1 d₁=4且d₂≤4。由公式(7)可得

$ 6{{n}_{4}}=p\left( p-1 \right)\left( p-2 \right)+q\left( q-1 \right)\left( q-2 \right) $

(8)

把公式(8)代入公式(4)可得

$ \begin{matrix} {{n}_{3}}=-\frac{1}{2}p\left( p-1 \right)\left( p-3 \right)- \\ \frac{1}{2}q\left( q-1 \right)\left( q-3 \right)<0 \\ \end{matrix} $

这与n₃≥0矛盾。

情形2.2 d₁>4且d₂=4。由公式(7)可得

$ \begin{matrix} 6{{n}_{4}}=p\left( p-1 \right)\left( p-2 \right)+q\left( q-1 \right)\left( q-2 \right)\ - \\ \left( {{d}_{1}}-1 \right)\left( {{d}_{1}}-2 \right)\ \left( {{d}_{1}}-3 \right) \\ \end{matrix} $

(9)

把公式(9)代入公式(4)可得

$ \begin{matrix} {{n}_{3}}=\frac{1}{2}\left( {{d}_{1}}-1 \right)\left( {{d}_{1}}-2 \right)\ \left( {{d}_{1}}-4 \right)- \\ \frac{1}{2}p\left( p-1 \right)\left( p-3 \right)-\frac{1}{2}q\left( q-1 \right)\left( q-3 \right) \\ \end{matrix} $

由d₁≤p+1和q≥4可得n₃<0，这也与n₃≥0矛盾。

情形2.3 d₁>4且d₂>4。由公式(7)可得

$ {{n}_{4}}=\left( \begin{matrix} p \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix} q \\ 3 \\ \end{matrix} \right)-\left( \begin{matrix} {{d}_{1}}-1 \\ 3 \\ \end{matrix} \right)-\left( \begin{matrix} {{d}_{2}}-1 \\ 3 \\ \end{matrix} \right) $

(10)

把公式(10)代入公式(4)可得

$ \begin{matrix} {{n}_{3}}=\frac{1}{2}\left( {{d}_{1}}-1 \right)\left( {{d}_{1}}-2 \right)\ \left( {{d}_{1}}-4 \right)-\frac{1}{2}p\left( p-1 \right)\cdot \\ \left( p-3 \right)+\frac{1}{2}\left( {{d}_{2}}-1 \right)\left( {{d}_{2}}-2 \right)\ \left( {{d}_{2}}-4 \right) \\ \end{matrix} $

(11)

已证得了d₁≤p+1和d₂≤q+3。首先从下面四个方面考虑d₁<p+1情况，也就有n_p+1=0。

情形2.3.1 假设d₁=p且d₂=q+3，有公式(10)和(11)可得

$ \begin{matrix} {{n}_{4}}=-\frac{1}{2}{{p}^{2}}-\frac{3}{2}p+1-{{q}^{2}} \\ {{n}^{3}}=-\frac{3}{2}{{p}^{2}}\frac{11}{2}p-5+3{{q}^{2}}-2q= \\ -\frac{1}{2}\left( p-2 \right)\left( 3q-5 \right)+3{{q}^{2}}-2q \\ \end{matrix} $

(12)

由n₄≥0可得$ p\ge \frac{3+\sqrt{8{{q}^{2}}+1}}{2} $，把p代入(12)式可得

$ \begin{matrix} \begin{matrix} {{n}^{3}}\le -\frac{1}{2}\left( \frac{3+\sqrt{8{{q}^{2}}+1}}{2}-2 \right)\cdot \\ \left( 3\times \frac{3+\sqrt{8{{q}^{2}}+1}}{2}-5 \right)+ \\ \end{matrix} \\ 3{{q}^{2}}-2q=-\frac{1}{2}+\frac{1}{2}\sqrt{8{{q}^{2}}+1}-2q<0 \\ \end{matrix} $

这与n₃≥0矛盾。

情形2.3.2 假设d₁=p-1且d₂=q+3，有公式(10)和(11)可得

$ \begin{matrix} {{n}_{4}}={{p}^{2}}-4p-{{q}^{2}}+4=\left( p-2-q \right)\left( p-2+q \right) \\ {{n}^{3}}=-3{{p}^{2}}+14p-16+3{{q}^{2}}-2q= \\ -\left( p-2 \right)\left( 3p-8 \right)+3{{q}^{2}}-2q \\ \end{matrix}\ $

(13)

由n₄≥0得p≥q+2。将p≥q+2代入上式n₃中可得n₃≤-q(3q-2)+3q²-2q=0，由此可得p=q+2且n₃=n₄=0。现有d₁=p-1=q+1<d₂=q+3与d₁≥d₂矛盾。

情形2.3.3 假设d₁≤p-2且d₂=q+3，有q+3=d₂≤d₁≤p-2，即p≥q+5。将d₁≤p-2和d₂=q+3代入(11)式得

$ \begin{matrix} {{n}^{3}}\le -\frac{9}{2}{{p}^{2}}+\frac{51}{2}p-37+3{{q}^{2}}-2q\le \\ -\frac{9}{2}{{\left( q+5 \right)}^{2}}+\frac{51}{2}\left( q+5 \right)-37+3{{q}^{2}}-2q\le \\ -\frac{3}{2}{{q}^{2}}-\frac{43}{2}q-22<0 \\ \end{matrix} $

(14)

这也与n₃≥0矛盾。

情形2.3.4 假设d₁≤p且d₂≤q+3，由(11)式和p≥q+1得

$ \begin{matrix} {{n}^{3}}\le -\frac{3}{2}{{p}^{2}}+\frac{11}{2}p-4+\frac{3}{2}{{q}^{2}}-\frac{5}{2}q= \\ -\frac{1}{2}\left( p-1 \right)+\left( 3p-8 \right)+\frac{3}{2}{{q}^{2}}-\frac{5}{2}q\le \\ -\frac{1}{2}q\left( 3q-5 \right)+\frac{3}{2}{{q}^{2}}-\frac{5}{2}q=0 \\ \end{matrix} $

(15)

由n₃=0，得出d₁=p，d₂=q+2和p=q+1。这时有d₁=p=q+17lt;q+2=d₂与d₁≥d₂矛盾。

由上述讨论，可以得到d₁=p+1，即n_p+1≥1。现假设n_p+1≥2，即图G'中至少存在2个度为p+1的结点。应用公式(5)得

$ \begin{matrix} \left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)=\sum\limits_{i=1}^{{{d}_{1}}}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}\ge } \\ 2\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)+\sum\limits_{i=1}^{P}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}} \\ \end{matrix} $

进一步得到

$ \left( \begin{matrix} q+1 \\ 3 \\ \end{matrix} \right)-\left( \begin{matrix} p+1 \\ 3 \\ \end{matrix} \right)\ge \sum\limits_{i=1}^{P}{\left( \begin{matrix} i \\ 3 \\ \end{matrix} \right){{n}_{i}}\ge }0 $

这与q<p矛盾，因此n_p+1=1。

由q≥4，再联合公式(10)和(11)得出d₂=q+1。由公式(5)得，当i=3,4,…,q,q+2,…,p时n_i=0。由公式(1)和(2)得n₁=p+q和n₂=n-2，因此得

$ \deg \left( G' \right)=\left( p+1,q+1,\overbrace{2,\ldots ,2}^{n-2},\overbrace{1,\ldots ,1}^{p+q} \right) $

定理1 设图G=H(p,n,q)满足n≥4且p>q≥2，则G由Laplacian谱确定的。

证明：设图G'是图G的L-同谱图。由引理2.3，G'是度序列为$\deg \left( G' \right)=\left( p+1,q+1,\overbrace{2,\ldots ,2}^{n-2},\overbrace{1,\ldots ,1}^{p+q} \right) $的似双星树，下面证明图G'与图G是同构的。

首先，假设图G'中度大于2的结点是相邻的。且与度为q+1的结点相邻的悬挂点有q-a个，与度为p+1的结点相邻的悬挂点有p-b个，其中a和b是满足0≤a≤q和0≤b≤p的非负整数。n'_i记为线图$ \ell \left( G' \right) $中度为i的结点的个数。则有n'₁=a+b，n'_p+q=1，n'_p+1=b，n'_p=p-b，n'_q+1=a，n'_q=p-a，n'₂=n-2-a-b和n'_j=0(j∉{1,2,p,q,p+1,q+1,p+q})。

另一方面，容易得到图G的线图$\ell \left( G \right)$的度序列$\deg \left( \ell \left( G \right)\ =\left( p+1,q+1,\overbrace{p,\ldots ,p}^{p},\overbrace{q,\ldots ,q}^{q},\overbrace{2,\ldots ,2}^{n-3} \right) \right.$

又$\ell \left( G \right)$和$ \ell \left( G' \right) $是A-同谱图，由引理1的2)和3)，$\ell \left( G \right)$和$ \ell \left( G' \right) $具有相同的边数以及长度为4的闭回路的数目。显然，它们含有的长度为4的圈图的数目相同。

再由引理2得，$\ell \left( G \right)$和$ \ell \left( G' \right) $中长度为2的导出路的数目相同，即

$ \begin{matrix} \left( \begin{matrix} p+1 \\ 2 \\ \end{matrix} \right)+\left( \begin{matrix} q+1 \\ 2 \\ \end{matrix} \right)+p\left( \begin{matrix} p \\ 2 \\ \end{matrix} \right)+q\left( \begin{matrix} q \\ 2 \\ \end{matrix} \right)+\left( n-3 \right)\left( \begin{matrix} 2 \\ 2 \\ \end{matrix} \right)= \\ \left( \begin{matrix} p+q \\ 2 \\ \end{matrix} \right)+b\left( \begin{matrix} p+1 \\ 2 \\ \end{matrix} \right)+\left( p-b \right)\left( \begin{matrix} p \\ 2 \\ \end{matrix} \right)+a\left( \begin{matrix} q+1 \\ 2 \\ \end{matrix} \right)+ \\ \left( p-a \right)\left( \begin{matrix} q \\ 2 \\ \end{matrix} \right)+\left( n-2-a-b \right)\left( \begin{matrix} 2 \\ 2 \\ \end{matrix} \right) \\ \end{matrix} $

(16)

简化式子(16)得

$ \left( p-1 \right)\left( q-1 \right)+b\left( p-1 \right)+a\left( q-1 \right)=0 $

又p>q≥2，0≤a≤q和0≤b≤p。很容易验证

$ \left( p-1 \right)\left( q-1 \right)+b\left( p-1 \right)+a\left( q-1 \right)\ne 0 $

由此得出矛盾。

现假设图G'中度大于2结点是不相邻的，如图 2所示，其中l₁，l'_i(1≤i≤a)和l″_j(1≤j≤b)都是正整数。

再次假设与度为q+1的结点相邻的悬挂点有q-a个，与度为p+1的结点相邻的悬挂点有p-b个，其中a和b是满足0≤a≤q和0≤b≤p的非负整数。通过计算图G和G'中结点的个数，可以到

$ {{l}_{1}}+\sum\limits_{i=1}^{a}{l{{'}_{i}}+\sum\limits_{j=1}^{b}{l'{{'}_{j}}+\left( p+q \right)=n+p+q}} $

即

$ {{l}_{1}}+\sum\limits_{i=1}^{a}{l{{'}_{i}}+\sum\limits_{j=1}^{b}{l'{{'}_{j}}=n}} $

再次令n'_i为线图$ \ell \left( G' \right) $中度为i的结点的个数。则有n'₁=a+b，n'_p+1=b+1，n'_p=p-b，n'_q+1=a+1，n'_q=p-a，n'₂=n-3-a-b和n'_j=0(j∉{1,2,p,q,p+1,q+1})。进行与上述类似的讨论，$\ell \left( G \right)$和$ \ell \left( G' \right) $中长度为2的导出路的数目相同，则

$ \begin{matrix} \left( \begin{matrix} p+1 \\ 2 \\ \end{matrix} \right)+\left( \begin{matrix} q+1 \\ 2 \\ \end{matrix} \right)+p\left( \begin{matrix} p \\ 2 \\ \end{matrix} \right)+q\left( \begin{matrix} q \\ 2 \\ \end{matrix} \right)+\left( n-3 \right)\left( \begin{matrix} 2 \\ 2 \\ \end{matrix} \right)= \\ \left( b+1 \right)\left( \begin{matrix} p+1 \\ 2 \\ \end{matrix} \right)+\left( p-b \right)\left( \begin{matrix} p \\ 2 \\ \end{matrix} \right)+\left( a+1 \right)\left( \begin{matrix} q+1 \\ 2 \\ \end{matrix} \right)+ \\ \left( q-a \right)\left( \begin{matrix} q \\ 2 \\ \end{matrix} \right)+\left( n-3-a-b \right)\left( \begin{matrix} 2 \\ 2 \\ \end{matrix} \right) \\ \end{matrix} $

简化(18)式得a(q-1)+b(p-1)=0。于是可得a=0和b=0，把a=0和b=0代入(14)式得l₁=n。由此可得图G'同构于图G。证明结束。

结合命题1和定理1，有以下结论：

定理2 所有的似双星树H(p,n,q)都是由Laplacian谱确定的。

由于一个图的L谱可以确定它的补图^[32]的L谱，那么由定理2可得出下面的结论。

推论 1 任意似双星树H(p,n,q)的补图都是由Laplacian谱确定的。

3 结束语

1)当p=q时，即图H(p,n,q)是由Laplacian谱确定的。

2)当p≠q时，问题的关键点是确定图的度序列deg(G')，其中图G'与图H(p,n,q)是L-同谱图。本文在引理3中解决了这个问题，并证明了所有似双星树H(p,n,q)是由Laplacian谱确定的，得到了这个问题的完整解决。