盧鵬麗,欒 睿,劉文智
(蘭州理工大學 計算機與通信學院,甘肅 蘭州 730050)
圖G的剖分圖S(G)是在圖G的每條邊上添加一個新的頂點得到的.
定義1[12]設(shè)兩個圖G1和G2,將S(G1)中新添加的頂點與S(G2)中新添加頂點全部相連接,構(gòu)造的圖稱為剖分邊邊聯(lián)圖,記為G1⊕G2.
定義2[13]設(shè)兩個圖G1和G2,將S(G1)中原有頂點與S(G2)中原有頂點全部相連接,構(gòu)造的圖稱為剖分點點聯(lián)圖,記為G1◇G2.
定義3[13]設(shè)兩個圖G1和G2,將S(G1)中原有頂點與S(G2)中新添加頂點全部相連接,構(gòu)造的圖稱為剖分點邊聯(lián)圖,記為G1⊙G2.
引理1[14]設(shè)G是一個r-正則圖,其鄰接矩陣為A(G),關(guān)聯(lián)矩陣為R(G),圖G的線圖記為L(G),I是與圖G同維數(shù)的單位矩陣,則
R(G)R(G)T=A(G)+rI
R(G)TR(G)=A(L(G))+2I
設(shè)J為全一矩陣,則
JR(G)=2J=R(G)TJ
JR(G)T=rJ=R(G)J.
spec(L(G))=
且Z是特征值-2所對應(yīng)的特征向量當且僅當RZ=0,其中R是圖G的關(guān)聯(lián)矩陣.
定理1設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分邊邊聯(lián)圖G1⊕G2的距離譜為
4) 矩陣的四個特征值
證明由剖分邊邊聯(lián)圖的定義可知其距離矩陣D(G1⊕G2)可表示為
其中:Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.
設(shè)Xij,i=1,2,j=2,3,…,ni為矩陣A(Gi)的特征值λij≠ri所對應(yīng)的特征向量,即A(Gi)Xij=λijXij.則Xij和全一向量J正交,由引理1可知:
求解上述方程組可得
j=2,3,…,n1
求解上述方程組可得
j=2,3,…,n2
證畢
定理2設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分邊邊聯(lián)圖G1⊕G2的距離拉普拉斯譜為
16r2+16
5) 矩陣的四個特征值
證明由剖分邊邊聯(lián)圖的定義可知其距離拉普拉斯矩陣DL(G1⊕G2)可表示為
其中
4J+2A(G2)
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣,J為全一矩陣,I為單位矩陣.證明方法同定理1.
定理3設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分邊邊聯(lián)圖G1⊕G2的距離無符號拉普拉斯譜為
5) 矩陣的四個特征值
證明由剖分邊邊聯(lián)圖的定義可知其距離無符號拉普拉斯矩陣DQ(G1⊕G2)可表示為
其中
4J-2A(G2)
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理4設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點點聯(lián)圖G1◇G2的距離譜為
1) -2(λ1j+r1+1),j=2,3,…,n1;
2) -2(λ2j+r2+1),j=2,3,…,n2;
4) 矩陣的四個特征值
證明由剖分點點聯(lián)圖的定義可知其距離矩陣D(G1◇G2)可表示為
其中:Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理5設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點點聯(lián)圖G1◇G2的距離拉普拉斯譜為
5) 矩陣的四個特征值
證明由剖分點點聯(lián)圖的定義可知其距離拉普拉斯矩陣DL(G1◇G2)可表示為
其中
2A(L(G2))
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理6設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點點聯(lián)圖G1◇G2的距離無符號拉普拉斯譜為
4λ1jn2+16λ1jr1+16λ1j+
n1n2r1+n1n2r2+2n1n2-
2λ2jn2r2-4λ2jn2+16λ2jr2+16λ2j+
n1n2r1+n1n2r2+2n1n2-
5) 矩陣的四個特征值
證明由剖分點點聯(lián)圖的定義可知其距離無符號拉普拉斯矩陣DQ(G1◇G2)可表示為
其中
4J-2A(L(G1)
4J-2A(L(G2))
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理7設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點邊聯(lián)圖G1⊙G2的距離譜為
2) -2λ2j-2r2-2,j=2,3,…,n2;
5) 矩陣的四個特征值
證明由剖分點邊聯(lián)圖的定義可知其距離矩陣D(G1⊙G2)可表示為
其中:Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理8設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點邊聯(lián)圖G1⊙G2的距離拉普拉斯譜為
5) 矩陣的四個特征值
證明由剖分點邊聯(lián)圖的定義可知其距離拉普拉斯矩陣DL(G1⊙G2)可表示為
其中
N7=3n1+n1r1+n2+n2r2-4
C5=(3n1+n1r1+3n2+2n2r2-4r2)I-4J+
2A(L(G2))
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.
定理9設(shè)Gi是有ni個頂點的ri-正則圖,其鄰接矩陣A(Gi)對應(yīng)的鄰接譜為{ri=λi1,λi2,λi3,…,λini},i=1,2.則剖分點邊聯(lián)圖G1⊙G2的距離無符號拉普拉斯譜為
n1n2r1+n1n2r2+2n1n2-
5) 矩陣的四個特征值
證明由剖分點邊聯(lián)圖的定義可知其距離無符號拉普拉斯矩陣DQ(G1⊙G2)可表示為
其中
N9=3n1+n1r1+n2+n2r2-8
C6=(3n1+n1r1+3n2+2n2r2-4r2-8)I+4J-
2A(L(G2))
Ri是圖Gi,i=1,2的關(guān)聯(lián)矩陣;J為全一矩陣;I為單位矩陣.證明方法同定理1.